# On the List Monad

This post is a short demonstration of both the List monad, and an explanation of some of the monadic functions in the Prelude and Control.Monad libraries. It assumes you have *some* knowledge of Monads in a Haskell context, but are not entirely comfortable yet.

Our guiding example is to find the moore neighbourhood of a cell on a 2D grid, which is defined as the cell itself, plus the eight cells surrounding it.

## Algorithm

We’re going to assume our grid is two-dimensional. We’ll extend this later. Our 2D moore function should take a single 2D point and return a list of points. Given the coordinate `(0, 0)`

we expect our function to give us the following list of 9 coordinates: `[(-1,-1), (-1, 0), (-1, 1), (0, 0), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]`

We know, then, that our function should have the following type signature:

`moore2D :: Num a => (a, a) -> [(a, a)]`

Our algorithm will be a simple translation of the moore neighborhood around the origin. Given a target coordinate, `c`

:

- Generate the moore neighbourhood of
`(0, 0)`

- Add our
`c`

to each point in this neighbourhood

So first we need to generate those offsets. The one-dimensional case is very easy, and we’ll just write it out:

`offsets1D = [-1, 0, 1]`

This is our **x** dimension, and it corresponds to the cells **W, C, and E** in the diagram above.

2D is a little harder. Our approach:

- For each cell in the 1D case, for example
**W** - Generate 3 new 2D coordinates, one for each 1D offset in the
**y**dimension, e.g.`[(w, -1), (w, 0), (w, 1)]`

. - Combine the results

So our first, rather ugly, attempt, ends up looking a lot like the following. Note that we could have written `concatMap`

instead of `concat $ map`

.

`offsets2D' = concat $ map (\x -> map (\y -> (x, y)) offsets1D) offsets1D`

We can write this a lot more neatly with a list comprehension:

`offsets2Dlist = [ (x, y) | x <- offsets1D, y <- offsets1D ]`

## Interlude: The List Monad as modelling nondeterminism

A quick detour now onto a certain way of thinking about the List Monad. You may have come across the notion of Monads being a *context* for a certain type- this fits the List-as-nondeterminism monad quite well. Consider a List as encapsulating *all possible values* for a nondeterministic function_, rather than just the normal single value. When composing these nondeterministic results, we expect to see an explosion in possible values.

For example, let’s take a coin toss, `coin`

, which returns either Heads or Tails. When we take values from two independent flips, we end up with all four possible outcomes.

```
data Coin = Heads | Tails
flipCoin = [Heads, Tails]
flipTwice = [ (x, y) | x <- flipCoin, y <- flipCoin ]
-- The results of running flipTwice:
-- [(Heads,Heads),(Heads,Tails),(Tails,Heads),(Tails,Tails)]
```

In fact, there’s a whole library based on this called “Probabilistic Functional Programming”. If you’re interested, you should check it out here.

It turns out, the list comprehension is just syntactic sugar for do-notation. That means we can rewrite `flipTwice`

using `do`

:

```
flipTwice = do
x <- flipCoin
y <- flipCoin
return (x, y)
```

The takeaway from this little segue is that the List monad’s implementation of the bind `(>>=)`

operator will evaluate the bound function for each of the values in the list, and then concatenate the results into a new list.

If you haven’t already, you should definitely look at its implementation here.

## Desugaring the List Comprehension

Back to the Moore neighborhood.

As we now know, the list comprehension syntax is actually just syntactic sugar for do-notation. That means we can translate it to this:

```
offsets2Dmonadic = f offsets1D offsets1D
where f m1 m2 = do
x <- m1
y <- m2
return (x, y)
```

Here we’ve created a helper function, `f`

, which takes two lists, `m1`

and `m2`

, and then performs our “list comprehension”. Hang on, though! `f`

doesn’t use any list-specific features- we’re treating it just like a monad- so `m1`

and `m2`

can be *any* monad, not just lists. That means its type is:

`f :: Monad m => m a -> m b -> m (a, b)`

Well, there’s already a function we can use to do this. It’s called liftM2, and we almost implemented it exactly. It’s slightly more general, though. Instead of creating a tuple from x and y, it applies a binary function passed as the first argument. Here’s how it’s defined in `Control.Monad`

:

```
liftM2 :: (Monad m) => (a1 -> a2 -> r) -> m a1 -> m a2 -> m r
liftM2 f m1 m2 = do
x1 <- m1
x2 <- m2
return (f x1 x2)
```

So that means we can rewrite our whole function quite simply with liftM2:

`offsets2Dlift = liftM2 (,) offsets1D offsets1D`

## Generalising to n-dimensions

Now, we want to make our function work in more than just two dimensions. All we have to do is repeat the step that made it work from 1 dimension to 2. Namely, for each coordinate in the 1D case, get all 2D coordinates with that x value. To get 3D, we take each coordinate in the 2D case, and return all 3D coordinates with those values for x and y. Simple!

All we need to do is keep repeating that step as long as we have dimensions to add to our resulting coordinates. First, though, let’s take a step back and look again at a slightly simplified monadic version of offsets2D. Note that we’re now using a *list* as our resulting coordinate.

```
offsets2Dmonadic = do
x <- offsets1D
y <- offsets1D
return (x:y:[])
```

We must note that this function desugars to the following:

`offsets2D' = offsets1D >>= (\x -> offsets1D >>= (\y -> return (x:y:[])))`

Here we can start to see how to solve the problem. To get the 3D case from above we can apply a liberal sprinkling of bind. In fact, what we really want is some kind of fold using `(>>=)`

across a list of offsets1D.

So, for a 2-dimensional neighbourhood around zero, we want to start with the 1D, `[[-1], [0], [1]]`

, then explore all possibilities of y-coordinate for each. Note that each 1D coordinate is wrapped in a list: that’s because the type of each coordinate needs to remain the same as we fold- `[-1]`

is the same type as `[-1, 0]`

.

We need a function that takes a value and adds it as a new dimension to a coordinate. That’s pretty simple, it’s just the list constructor `(:)`

.

That means our function to fold over a list should look like this:

```
foldee m m' = do
x <- m -- value of coordinate in new dimension
xs <- m' -- value of rest of coordinate
return (x:xs) -- Return the new coordinate with extra dimension
```

Now we just have to fold it across the list! We add the first case of `[[]]`

so that the fold with the first dimension gives us `[[-1], [0], [1]]`

. You might think of `[[]]`

as being a deterministic result (just a single value) wrapped in the nondeterminism monad. It’s an empty list because it’s zero-dimensional.

Cool, we can write the function to chain our monads together using the `foldee`

function:

```
chainM :: Monad m => [m a] -> m [a]
chainM ms = foldr foldee (return []) ms
```

We can see this working if we run the following in GHCi:

```
Main> chainM [offsets1D, offsets1D]
[[-1,-1],[-1,0],[-1,1],[0,-1],[0,0],[0,1],[1,-1],[1,0],[1,1]]
```

And now it’s just a small step to get the n-dimensional function to generate our offsets, by using replicate to generate a repeated list of `offsets1D`

:

`offsets' n = chainM $ replicate n offsets1D`

You’ll also see that we modified the base case in `chainM`

to be `(return [])`

instead of `[[]]`

. That allows our function to generalise to all monads again! As you’ve probably guessed, this function *already exists* in the Prelude, except instead of `chainM`

, it’s called `sequence`

. It’s implementation is almost identical to what we wrote:

```
sequence :: Monad m => [m a] -> m [a]
sequence ms = foldr k (return []) ms
where k m m' = do { x <- m; xs <- m'; return (x:xs) }
```

But wait! There’s more! We’ve used the `replicate`

function to make a list of `offsets1D`

repeated `n`

times, and then applied sequence to it. Thanks to the generality of Monads, that function exists already too, and it’s called `replicateM`

. Here’s it’s definition:

```
replicateM :: (Monad m) => Int -> m a -> m [a]
replicateM n x = sequence (replicate n x)
```

So that means, at long last, we can define the function to generate the moore neighbourhood for the origin in n dimensions:

```
offsets :: Num a => Int -> [[a]]
offsets n = replicateM n [-1, 0, 1]
```

Simple!

Translating of those coordinates to get the Moore neighbourhood of the point we’re actually after is pretty trivial, but i’ve included it for completeness:

```
moore :: Num a
=> [a] -- ^ target coordinate
-> [[a]] -- ^ List of points in its moore neighbourhood
moore xs = map (zipWith (+) xs) originOffsets
where n = length xs -- Find the number of dimensions in the coord
originOffsets = replicateM n [-1, 0, 1]
```

And we’re done!

Paul —