Much Ado About Monads – List Edition
In the previous installment in my quest to make monads a little more approachable, I covered the maybe monad and how it can apply as a general design pattern for dealing with lookups that may or may not succeed. We covered how as a functional design pattern, we can use these monads to easily compose functions together in such a way that makes sense. This time, we’ll look at the list monad, and how you may already be using it without knowing it.
What’s the Problem?
In order to understand the list monad, we first need to understand the problem it’s trying to solve. In our last example with the maybe, we wanted to represent whether we had a value or not. This time, we might want to return any number of results that we don’t know ahead of time. Taking an example from the Real World Haskell book, let’s take an example of trying to find all combinations of numbers that when multiplied together, equal a given number. First, we’ll do it in a typical imperative style.
{
var list = new List<KeyValuePair<int, int>>();
foreach(var x in Enumerable.Range(1, number))
{
foreach(var y in Enumerable.Range(x, number))
{
if(x * y == number)
list.Add(new KeyValuePair<int, int>(x, y));
}
}
return list;
}
We can then run any number of scenarios to show that it works properly such as an example to 45:
3 - 15
5 - 9
Much as we saw in our Maybe example, there is a pattern we’re seeing here with the for/foreach loops. Exploring functional programming, once again monads can be used to abstract this uniform behavior.
The List Monad
From the Haskell page on monads, the list monad is described as the following:
The List monad embodies the strategy of combining a chain of non-deterministic computations by applying the operations to all possible values at each step. It is useful when computations must deal with ambiguity. In that case it allows all possibilities to be explored until the ambiguity is resolved.
The explanation is simple enough, just as I explained above. Before we look at an example, let’s now take a look at the definition of the list monad before we get started.
m >>= k = foldr ((++) . k) [] m
m >> k = foldr ((++) . (\ _ -> k)) [] m
return x = [x]
fail _ = []
What this tells us is that the bind operation is applying k to every item in the list then doing a concatenation to the accumulator in a right fold. Just as easily, we could have written it as concat (map f x) instead. Taking the above sample of code in the imperative style and rewrite it using monadic syntax such as the following:
multiplyTo n = do
x <- [1..n]
y <- [x..n]
guarded (x * y == n) $ return (x, y)
guarded :: Bool –> [ a ] –> [ a ]
guarded True xs = xs
guarded False _ = []
Taking this code and running it with an example of 45 once again yields us the following results:
[(1,45),(3,15),(5,9)]
Knowing what we know now about monads in Haskell, can the same apply in F#? The answer of course is yes!
Listing F#
If we understand how I used a builder in the last example with the maybe, it should be rather simple to translate what I did there to using lists instead. In order to do so, I’m going to create some standard operators I’ll use later on in my examples:
module ListOperators =
let bindM (l:'a list) (f:'a -> 'b list) =
List.concat (List.map f l)
let returnM (l:'a) : 'a list = [l]
let mzero = []
let mplus = (@)
let (>>=) l f = bindM l f
let rec foldM (f:'a -> 'b -> 'a list) (a:'a) : 'b list -> 'a list = function
| [] -> returnM a
| x::xs -> f a x >>= (fun fax -> foldM f fax xs)
These define some of the basic operators such as bind and return which I’ll need later. The mzero and mplus are operators that are holdovers from the MonadPlus type class in the Haskell version. I also included the foldM function as well for an example a little later. Now that we have some of the basic functions defined, let’s now define our builder:
member x.Bind(l, f) = bindM l f
member x.Return(l) = returnM l
member x.Delay(f) = f()
member x.Zero() = []
let listM = new ListBuilder()
I also included the Zero function as well to de-sugar an empty else branch of an if/else statement. Now that our builder is define, we can now use it to implement the multiplyTo function as we had above:
match b with
| true -> xs
| false -> []
let multiplyTo n =
listM { let! x = [1..n]
let! y = [x..n]
return! guarded (x * y = n) [x, y]
}
let mResult =
multiplyTo 45 |>
List.iter (fun t -> printfn "%d-%d" (fst t) (snd t))
Iterating our results will give us the exact answer once again. Nice and simple example, but let’s try something a bit more complex. On the list monad Haskell page, there is the canonical use for parsing ambiguous grammars. We can parse data into hex values, decimal values and words containing only alpha-numeric characters. Because hex digits overlap with decimal and alpha-numeric, hence this leads to an ambiguous grammar. Let’s take that example from the page and use our knowledge of the list monad to put it to work.
First, let’s define some Char functions that we need to accomplish this goal:
open System
let isAlpha = Char.IsLetter
let isDigit = Char.IsDigit
let isHexDigit c =
isDigit c || c >= 'A' && c <= 'F' ||
c >= 'a' && c <= 'f'
let digitToInt : char -> int = function
| c when isDigit c -> int c - int '0'
| c when c >= 'a' && c <= 'f' -> int c - int 'a' + 10
| c when c >= 'A' && c <= 'F' -> int c - int 'A' + 10
| c -> failwith ("Char.digitToInt: not a digit "
Now we can define the rest of our logic as follows:
/// we can parse three different types of terms
type Parsed =
| Digit of int
| Hex of int
| Word of string
/// attempts to add a character to the parsed
/// representation of a hex digit
let parseHexDigit (p:Parsed) (c:char) : Parsed list =
listM { match p with
| Hex n -> if Char.isHexDigit c then
return (Hex ((n * 16) +
(int (Char.digitToInt c))))
else
return! mzero
| _ -> return! mzero
}
/// attempts to add a character to the parsed
/// representation of a decimal digit
let parseDigit (p:Parsed) (c:char) : Parsed list =
listM { match p with
| Digit n -> if Char.isDigit c then
return (Digit ((n * 06) +
(int (Char.digitToInt c))))
else
return! mzero
| _ -> return! mzero
}
/// attempts to add a character to the parsed
/// representation of a word
let parseWord (p:Parsed) (c:char) : Parsed list =
listM { match p with
| Word s -> if Char.isDigit c then
return (Word (s + (string c)))
else
return! mzero
| _ -> return! mzero
}
/// tries to parse the digit as a hex value,
/// a decimal value and a word
let parse (p:Parsed) (c:char) : Parsed list =
(parseHexDigit p c) @ (parseDigit p c) @ (parseWord p c)
/// parse an entire String and return a list of the
/// possible parsed values
let parseArg (s:string) : Parsed list =
listM { let! init = (returnM (Hex 0))
@ (returnM (Digit 0))
@ (returnM (Word ""))
return! foldM parse init (Seq.to_list s)
}
Running through a quick example, we are able to call the function passing in “123” to get the following result:
val it : ListMonad.Parsed list = [Hex 291; Digit 51; Word "123"]
There’s nothing stopping us from switching out the list implementation for a sequence version as it’s just as easy to implement. Ok, well, the F# stuff is interesting, but how relevant is it to the more imperative programmer using C#? That’s where LINQ comes into play.
Enter LINQ
As I’ve stated before, at the heart and soul of LINQ is the list monad. If we examine the bind operation from the Haskell and F# monads, you’ll notice an exact match in signature as follows:
(>>=) :: m a -> (a -> m b) -> m b
// F#
val Bind : 'a list -> ('a -> 'b list) -> 'b list
// C#
public static IEnumerable<U> SelectMany<T, U>(
this IEnumerable<T> xs,
The actual implementation of the SelectMany looks something like the following:
this IEnumerable<T> xs,
Func<T, IEnumerable<U>> k)
{
foreach (var x in xs)
foreach (var y in k(x))
yield return y;
}
Knowing this, we should be able to write our C# code much as we did above in the F# and Haskell way such as the following:
{
return from x in Enumerable.Range(1, number)
from y in Enumerable.Range(x, number)
where x * y == number
select new KeyValuePair<int, int>(x, y);
}
This method above yields us the same result as our imperative answer from above, but yet clean and without a lot of noise involved with loops and such. This is just a simple example of using the list monad, so I encourage you to do more digging on your own. The more you keep working with these functional abstractions such as the maybe and now the list, you’ll find more places where they may apply.
Conclusion
Now, I think through this careful exploration, you may have a better understanding of these design patterns or at least how you might be able to abstract some sort of uniform complexity such as this case with lists. There’s more to these patterns than just the maybe and the list, as there’s the error, continuation, state and others but also some interesting ones that are unique to F# in the async “workflow”. What I’m really trying to drive home in this series is that ideas from functional programming aren’t just for guys in lab coats or those at the universities, but for general line of business developers as well. Stepping out of that comfort zone that is C# or VB and into a more functional language will give you a greater appreciation of different styles and improve your day to day coding.