Comprehensive Monad Notation

by Nicolas Wu

Posted on 2 December 2010

Tags: Haskell

Recently, Nils Schweinsberg wrote a post which describes his work on a new GHC extension called monad comprehensions. I stumbled across the idea of monad comprehensions a while ago when I was looking at the definition of the list monad. In this article I’ll be looking at the list monad to describe the link between list comprehensions and the do notation.

The List Monad

The Monad class defines two functions return and (>>=) as follows:

class Monad m where
  return :: a -> m a
  (>>=) :: m a -> (a -> m b) -> m b

The instance of a monad for a list is quite straightforward, where the return simply wraps a value to become a singleton, and bind maps a function of type a -> [b] across the elements in a list and concatenates the result:

instance Monad List where
  return x = [x]
  xs >>= f = concatMap f xs

I find that the relationship between list comprehensions and the do notation is made quite clear by considering the following equation, which follows on directly from the definitions above:

xs >>= \x -> return (f x)

Here’s an interesting property that this equation satisfies when the monad in question is a list:

concatMap (\x -> return (f x)) xs = map f xs

We can prove this by induction. When the list is empty, the proof is trivial. If the list is not empty then we have:

concatMap (\x -> return (f x)) (x:xs)
  = {- definition of concatMap -}
concat (map (\x -> return (f x)) (x:xs))
  = {- definition of map -}
concat (return f x : map (\x -> return (f x)) xs)
  = {- definition of concat -}
return f x ++ concat (map (\x -> return (f x)) xs)
  = {- definition of return -}
[f x] ++ concat (map (\x -> return (f x)) xs)
  = {- [x] ++ xs = x : xs -}
f x : concat (map (\x -> return (f x)) xs)
  = {- definition of concatMap -}
f x : concatMap (\x -> return (f x)) xs
  = {- induction hypothesis -}
f x : map f xs
  = {- definition of map -}
map f (x:xs)

With this in mind, we can view the monadic bind as a list comprehension as follows:

xs >>= \x -> return (f x)
  == {- definition of (>>=) -}
concatMap (\x -> return (f x)) xs
  == {- concatMap (\x -> return f x) xs = map f xs -}
map f xs

It doesn’t take long to realise that map f xs is equivalent to the following list comprehension:

[ f x | x <- xs ]

Since this is a monad, it’s worth seeing how it can be written in terms of do notation:

do x <- xs
   return (f x)

The interesting point here is that the use of list comprehension notation, though restricted to lists, could easily be extended to encompass arbitrary monads.

A Little History

I was amazed when I first saw this connection, and was rather surprised that I hadn’t seen it mentioned before. A History of Haskell revealed that this notation for monads had made its way in, and back out, of the Haskell Report:

April 1997. The Haskell version 1.4 report was published (139 + 73 pages), edited by Peterson and Hammond. This was a tidy-up of the 1.3 report; the only significant change is that list comprehensions were generalised to arbitrary monads, a decision that was reversed two years later.

Apparently this removal of comprehension notation was due to the fact that generalising comprehensions to monads made errors arising from comprehensions difficult for novices to understand. I’m glad that it’s being considered as an extension to GHC, and I’m looking forward to playing around with comprehensions rather than do notation when describing monadic behaviour.

Comments