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.
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:
Our algorithm will be a simple translation of the moore neighborhood around the origin. Given a target coordinate,
- Generate the moore neighbourhood of
- Add our
cto 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:
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.
We can write this a lot more neatly with a list comprehension:
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.
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
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:
Here we’ve created a helper function,
f, which takes two lists,
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
m2 can be any monad, not just lists. That means its type is:
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
So that means we can rewrite our whole function quite simply with liftM2:
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.
We must note that this function desugars to the following:
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], , ], 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
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:
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], , ]. 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
We can see this working if we run the following in GHCi:
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
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:
But wait! There’s more! We’ve used the
replicate function to make a list of
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:
So that means, at long last, we can define the function to generate the moore neighbourhood for the origin in n dimensions:
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:
And we’re done!Paul —