List as a Monad

Much ink has been spilled on the subject of “Lists as Monads”. Just the fact that they are of course, not what it means for you. This doesn’t really seem surprising to me; there are better monads to use to describe how monads work. Additionally, lists have their own special functions for working with them; you don’t fmap a list, you just call map.

Presumably, Lists as Monads is something that seasoned Monadimancers understand. Maybe it’s some sort of rite of passage. But no more. Today I’ll shed light on the arcane mysteries of Lists as Monads.

Motivation

But first we need a problem to solve. For my example I’ll be using the cartesian product of two lists. The cartesian product of two sets (we’ll be using lists) is defined as:

A X B is the set of all ordered pairs (a, b) such that: a is a member of set A and b is a member of set B

…translated into Haskell we should get a function with the following signature:

cartProd :: [a] -> [b] -> [(a, b)]

How might this function look? Well, we’d need three functions. The first function should have the signature:

cartProd'' :: a -> b -> (a, b)

This function is pretty straight forward, it pairs an a and a b. Next we’d need the function:

cartProd' :: [b] -> a -> [(a, b)]

This function maps (cartProd'' a) over b, producing the list [(a, b)]. Finally, we need a function to tie it all together:

cartProd :: [a] -> [b] -> [(a, b)]

This function maps (cartProd' b) over a, then concats the resulting list of lists. An implementation might look like this:

cartProd :: [a] -> [b] -> [(a, b)] cartProd l r = concat $ map (cartProd'' r) l where cartProd' :: [b] -> a -> [(a, b)] cartProd' r l = map (cartProd''' l) r where cartProd'' :: a -> b -> (a, b) cartProd'' l r = (l, r)

Did you go cross-eyed? Not exactly the most concise function that’s ever been written. Surely there is a better way…

Binding Our Lists

You may remember a few weeks back I talked about using the Maybe Monad. The gist of that post being that if you’re inside a do block, you can treat your Maybe as if it were just a plain value. It turns out that we can do something similar with Lists.

The Monad instance for [] is somewhat complicated, but it’s operation is straight forward. If >>= takes a Monad a, a function that takes an a and returns a Monad b, and returns a Monad b, what happens if we bind a simple function to [1]?

Prelude> [1] >>= (\a -> return $ a + 1) [2]

…ok, so it added 1 to 1, and stuffed it into a list. Seems pretty straight forward. Let’s try something a little more complicated:

Prelude> [1, 2] >>= (\a -> return $ a + 1) [2,3]

…so this time it added 1 to each list node, as if we’d called map ((+) 1) [1, 2]. Let’s try something else:

Prelude> [1] >>= (\a -> [(a + 1), (a - 1)]) [2,0]

…this time we tried it in reverse. We bound [1] to a function that returns a list with two elements. The resulting list contained two elements. Again, nothing ground breaking here, but what if we do both?

Prelude> [1, 2] >>= (\a -> [(a + 1), (a - 1)]) [2,0,3,1]

…now we get a list with four elements: 1+1, 1-1, 2+1, and 2-1. To replicate this behavior we can’t just map the lambda over the original list. We need to add a call to concat. Let’s expand this our a bit further:

Prelude> [1, 2] >>= (\a -> [(a + 1), (a - 1)]) >>= (\b -> [b, b]) [2,2,0,0,3,3,1,1]

…all simple functions, but if we were to try to do this without the use of List’s monadic functions it’d become a mess like my cartProd function. Speaking of which…

The Better Way

Getting back to our original topic. Now that we have a feel for how List’s monadic interface works, how could we re-implement cartProd to not be terrible? Simple:

cartProd :: [a] -> [b] -> [(a, b)] cartProd l r = do l' <- l r' <- r [(l', r')]

I’m often hesitant to toot my own horn and call something I wrote “elegant”, but it’s hard to argue that this function isn’t. In three short lines, I managed to re-implement that nested monstrosity I wrote before. There is one fairly massive gotcha here…

In the first and second lines, we bind our two lists to a label. It’s important to note that the order of these matters. The lists will be cycled through from the bottom up. Meaning that for each element of l, all elements of r will be evaluated. For example, using our cartProd:

Prelude> cartProd [1,2] [3,4] [(1,3),(1,4),(2,3),(2,4)]

1 is paired with 3, then 1 is paired with 4, then 2 is paired with 3 and 2 is paired with 4. Were we to swap the order in which we bind l and r to look like this:

cartProd :: [a] -> [b] -> [(a, b)] cartProd l r = do r' <- r l' <- l [(l', r')]

Then the output would look like this:

Prelude> cartProd [1,2] [3,4] [(1,3),(2,3),(1,4),(2,4)]

1 is paired with 3, then 2 is paired with 3, then 1 is paired with 4, then 2 is paired with 4. Before the first element of the tuple was grouped together where here the second element is. For our purposes, both results are valid per the definition of cartesian product, but that may not hold for you so be careful.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: