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!