# 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 `concat`

s 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.