# 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:

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

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`

.

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

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

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

## 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
= [Heads, Tails]
flipCoin
= [ (x, y) | x <- flipCoin, y <- flipCoin ]
flipTwice
-- 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`

:

```
= do
flipTwice <- flipCoin
x <- flipCoin
y 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:

```
= f offsets1D offsets1D
offsets2Dmonadic where f m1 m2 = do
<- m1
x <- m2
y 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
= do
liftM2 f m1 m2 <- m1
x1 <- m2
x2 return (f x1 x2)
```

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

`= liftM2 (,) offsets1D offsets1D offsets2Dlift `

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

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

We must note that this function desugars to the following:

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

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:

```
= do
foldee m m' <- m -- value of coordinate in new dimension
x <- m' -- value of rest of coordinate
xs 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]
= foldr foldee (return []) ms chainM 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`

:

`= chainM $ replicate n offsets1D offsets' n `

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]
= sequence (replicate n x) replicateM 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]]
= replicateM n [-1, 0, 1] offsets n
```

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
= map (zipWith (+) xs) originOffsets
moore xs where n = length xs -- Find the number of dimensions in the coord
= replicateM n [-1, 0, 1] originOffsets
```

And we’re done!

Paul —