All Unkept
Posted in: Python, Haskell  —  July 26, 2006 at 09:59 PM

Understanding Monads Via Python List Comprehensions

by Luke Plant

An attempt to explain monads and their usefulness in Haskell, assuming only some simple knowledge of Python.

List comprehensions are a great Python feature that have been borrowed from Haskell/ML, and ultimately from set theory. As you probably know, they provide a convenient syntax for building lists from other lists or sequences:

>>> lst = [1, 2, 3]
>>> [x*2 for x in lst]
[2, 4, 6]

The alternative to the list comprehension is something like this:

>>> newlist = []
>>> for x in lst:
...     newlist.append(x*2)

List comprehensions remove this annoying bit of boilerplate, helping to give Python the conciseness we love. The list comprehension knows all about creating an empty initial list and appending values etc, so we don't have to do that each time.

While learning Haskell, I found list comprehensions a reassuring plateau of familiarity amidst the otherwise rather treacherous, alien landscape, but they also provide a way in to the impenetrable forest of 'Monads'. In Haskell, the above Python code looks very similar (at a GHCi interactive prompt, where Prelude> is the standard prompt):

Prelude> let lst = [1,2,3]
Prelude> [ x*2 | x <- lst ]
[2,4,6]

That should be pretty easy to understand if you know Python, but here is a full 'translation' of the list comprehension into English: unpack each value in the list 'lst' in turn, give it the label 'x', and for each one return 'x * 2' as a value in a new list.

Haskell has another way of implementing the same thing, though -- using its 'do' notation:

Prelude> do { x <- lst; return (x*2) }
[2,4,6]

The similarity with the above should be pretty obvious, and in fact it does exactly the same thing. You'll notice that the order is reversed so it is more like our English version, and matches an imperative style of thinking (do this, then that), whereas the list comprehension syntax reflects its origins in the mathematical notations of set theory.

However, there is one difference. While list comprehension are specific to creating lists, 'do' notation has no knowledge of lists at all. In fact, the only list in this expression is the input value 'lst'. So, to prove a point, let's eliminate even that bit, by creating a function out of this expression:

Prelude> let double val = do { x <- val; return (x*2) }

This is a definition of the function 'double', that takes a single value 'val'. (At the interactive prompt, we have to add the keyword 'let', which wouldn't be present in normal Haskell source code). We can now use our function as before:

Prelude> double [0,1,2]
[0,2,4]

GHCi doesn't complain about any of this, even though Haskell is statically typed and we haven't told it what type of thing val is. So what type of thing is val? We can ask GHCi using :type, but we'll have to do it indirectly, by asking it the type of our function double:

[WARNING: the next few paragraphs are a bit tricky, but it gets easier again soon - hang in there!]

Prelude> :type double
double :: (Monad m, Num a) => m a -> m a

Woah! What on earth does all that mean? Well, let's ignore the bit in brackets, and look at the end first:

m a -> m a

The arrow tells us we have a function (GHC has at least got that bit right), and it takes values of type m a and returns values of type m a. m a is a 'parameterised type' -- as a simplification, we can say that 'm' is a placeholder for a container type, and 'a' is a placeholder for the type of thing it contains. In the case of our input lst, m is a list (represented as [] usually) and a is an integer. This is normally written [Integer] (a list of integers), rather than [] Integer. In our instance, double took a list of integers and returned a list of integers.

But GHC knew that our function was more generic than simply operating on lists of integers. From the 'do' notation, and the lack of anything about lists, it deduced that 'm' can actually be any 'Monad'. From the use of multiplication in '* 2', it deduced that 'a' has to be restricted to numbers -- more specifically, a type which implements the 'Num' interface (which includes integers, fractional numbers etc). The (Monad m, Num a) => bit is just indicating these restrictions.

So, how did our 'double' function achieve the feat of unpacking the data from the list, doubling each item, and returning the data in a new list, all without knowing anything about lists? Well, by using the 'do' notation, it was implicitly using a set of methods that are defined in the 'Monad' interface. Since lists are instances of the Monad interface, and defines all the methods correctly, it just worked.

Are there other Monads that we could use instead of lists? Well, of course, or no-one would have bothered to create an interface if there was only a single instance of it. One example would be the Maybe monad, that contains either Nothing, or an actual value, written Just somevalue. The Maybe monad encapsulates a value that might be there, but might not, and the logic that if it contains Nothing, then any function operating on it will have to return Nothing too. So we can now do this:

Prelude> double Nothing
Nothing

Prelude> double (Just 1.5)
Just 3.0

Magic! Trying to do Nothing * 2 will give you a type error, but by using the Maybe monad, and our function that was generic over monads, we did it easily, with no extra work. Impressed?

In other languages you can create functions that work with different types of collections, by using, for example, the iterator protocol in Python, or the IEnumerable interface in C#. But here we have taken it to a higher level -- the Monad interface is like an abstraction of any kind of container.

Alternatively, Maybe and lists can both be thought of as encapsulating different strategies for computing values. Maybe handles the case of 0 or 1 values, while list can handle any number of values, and it tries them all. This in turn leads to the concept that a monadic value represents a computation -- a method for computing a value, bound together with its input value. This becomes especially important when you move on to 'State transformation' monads, such as the famous IO monad. In these cases, the container is actually a function (but just don't think about that if it hurts your head!).

So, in Haskell Monads are simply an interface for a very generic container, but an interface that is so important that it has special syntactic support in the language, similarly to how the iterator protocol and lists in Python have various bits of syntactic support (such as for, in, list comprehensions, etc). The interface is more abstract than that of collections, which makes it more difficult to understand, but more powerful too, and the syntactic sugar all the more sweet, as it is much more broadly applicable.

For instance, monads were used to write the Parsec parser library which ends up with a syntax that allows a pretty direct translation from BNF, and is in fact more readable. The parser monads know all about applying constraints, backtracking etc, in the same way that the list monad knows about how to take each element and apply the function to each one. Writing monads is hard, but it pays off as using them in Haskell is surprisingly easy, and allows you to do some very powerful things.

I hope that begins to explain why monads are useful. The next difficulty is understanding the methods that make up the Monad interface, which is beyond the scope of this article really, but I'll try to give an introduction.

You can already guess something about the Monad methods. One of them you have seen explicitly -- it's the 'return' method, responsible for packing things up into the monad. The other is called 'bind' or '>>=', and it does the 'unpacking' involved with the <- arrow in the do notation.

Actually, the 'bind' method doesn't really unpack and return the data. Instead, it is defined in such a way that it handles all unpacking 'internally', and you have to provide functions that always have to return data inside the monad. Why is this important? Well, some uses of monads, especially the IO monad, need to ensure that data can't 'escape', in order to be able to make certain guarantees that keep your program working as expected. Monads like Maybe and list are much less possessive -- they are quite happy for you to get the data out. But by defining the Monad interface in this way, it can handle both cases, and it turns out to be quite convenient for both.

What is the <- in the do notation then? It is simply some syntactic sugar that allows you to define the right kind of functions easily and painlessly. It looks very much like 'unpack this data from the monad so I can use it', so it helps conceptually. In fact, together with the rest of the body of the 'do' block it forms an anonymous lambda function, and we could write our double function something pretty much like this in Python:

def double(val):
    return val.bind(lambda x: val.return_(x*2))

(I've had to use return_ to avoid the clash with Python's 'return' keyword). Haskell's do notation eliminates the explicit call to bind, and the lambda, making it quite a bit easier to use. This becomes especially important when you have long 'do' blocks, and functions with multiple monadic input values. One final thing to say - you will be pleased to learn that in Haskell you can actually use whitespace (newlines and indentation) instead of semi-colons and braces! (OK, OK, calm down you Pythonistas at the back, that's enough cheering now ;-).

I've done a complete example implementation of the List and Maybe monads in Python, along with the double function as above, trying to stay close to how it works in Haskell. You can't really translate Haskell's type system, but Python can do a pretty good job of implementing this, partly due to the fact that non-instance methods can be polymorphic, unlike many other OOP languages. The code is also a nice example of how succinct functional style code often is -- there isn't a function more than 4 lines long.

Has this helped at all? I'd be interested in any feedback, or corrections. I'm a Haskell newbie myself, so I may have got some things wrong, in which case I'll pretend that I was simplifying things for the sake of clarity :-) .

Further reading

Updates

  • 2006-07-28: added a translation of the 'double' function into Python, to explain the do notation's implicit lambda.
  • 2006-08-15: added some Python code that implements the same thing in Python.
  • 2006-09-11: fixed some bugs in the downloadable Python code, and adding 'lifting' examples to it.

Comments §

blog comments powered by Disqus