How to Solve a Tricky Monad Problem

Graham Hutton [1] has a neat exercise to help learn monads:

Problem: Given a tree, can we label each node with a unique number?

Solution: Use a state monad to model a RAM-like counter. Traverse the tree, labelling each node with the current count and bumping the counter before recursing into the branches.

Book cover

The original tree is binary:

data Tree a = Leaf a | Node (Tree a) (Tree a)

The heart of Hutton's solution lies in the effectful mlabel function:

mlabel            :: Tree a -> ST (Tree (a,Int))
mlabel (Leaf x)   =  do n <- fresh
                        return (Leaf (x,n))
mlabel (Node l r) =  do l' <- mlabel l
                        r' <- mlabel r
                        return (Node l' r')

(Hutton uses ST here to mean a State monad on Int. It does not refer to state threads. See the postscript.)

Instead of a binary tree, suppose we lean on the one provided in the containers package, a so-called rose tree:

data Tree a = Node a [Tree a]

How should we rewrite mlabel? The following attempt [2] throws a compile error:

mlabel :: Tree a -> ST (Tree (a, Int))
mlabel (Node root children) = do
   n <- fresh
   return $ Node (root, n) 
            [lab | c <- children , lab <- mlabel c]

In the list comprehension, lab had better be of type Tree (a, Int) because that's what the rose-tree Node constructor expects.

Now look at lab <- mlabel c. The function mlabel returns an ST of Tree (a, Int), so lab on the left of the arrow should have type Tree (a, Int).

Everything seems to match.

What's broken?

(scroll down for the answer)

v

v

v

v

v

v

v

v

v

v

v

v

v

v

v

v

v

v

v

v

v

v

v

v

There are two effects: ST and list. Both of them are invoked in the list comprehension, but only one of them is allowed: list. The effects don't match!

(Yes, there's such a thing as monad comprehension that overloads the syntax. Being dimly aware of it is what tripped us up! A little knowledge can indeed mislead ....)

You can have c <- children in a list comprehension and a lab <- mlabel c in a monad comprehension, but they must be two separate comprehensions. Same with do-blocks: one do-block one effect.

Instead of [lab | c <- children, lab <- mlabel c], which doesn't typecheck because of mismatched effects; let's write [mlabel c | c <- children], which does typecheck and has the type [ST (Tree (a, Int))].

But we really want a list of trees, not a list of effectful trees. How do we go from [ST (Tree (a, Int))] to [Tree (a, Int)]?

If only there was a way to swizzle [ST ...] into ST [...] we could write

mlabel :: Tree a -> ST (Tree (a, Int))
mlabel (Node root children) = do
   n <- fresh
   newchildren <- ??? [mlabel c | c <- children]
   return $ Node (root, n) newchildren

Notice how close the correct answer is to the original binary tree solution:

mlabel            :: Tree a -> ST (Tree (a,Int))
mlabel (Node l r) =  do l' <- mlabel l
                        r' <- mlabel r
                        return (Node l' r')

So what's the missing piece in newchildren <- ??? [mlabel c | c <- children] ?

v

v

v

v

v

v

v

v

v

v

v

v

v

v

v

v

v

v

v

v

v

v

v

v

The sequence function! Which takes [m a] and return m [a], exactly what we wanted. So we get:

mlabel :: Tree a -> ST (Tree (a, Int))
mlabel (Node root children) = do
   n <- fresh
   newchildren <- sequence [mlabel c | c <- children]
   return $ Node (root, n) newchildren

BONUS: Idiomizing further, we could observe that the sequence of the list comprehension is really a list map followed by a sequence. That's exactly the definition of mapM, and thus: newchildren <- mapM mlabel children.

[1] http://www.cs.nott.ac.uk/~gmh/monads

[2] Gist on github

p.s. Hutton wants to drive home the point that state can be purely modelled as an endofunction (aka transformer) on the storage datum. Unfortunately, his naming of the monad as ST (for state transformer) will confuse folks once they start learning about the other ST (state thread) monad. Hutton's ST in real world haskell is just called State (in Control.Monad.State), which is in turn defined as a synonym of the StateT (monad!) transformer.

Kim-Ee Yeoh
Kim-Ee Yeoh hacks haskell for fun, profit, and beautiful code.

p.p.s. Does trying to figure out monads make you crawl up the wall?

Is it because the recommended resources are eye-glazing blocks of text? And the code? Alien and unpronounceable? The rare diagram? Cute, but only wraps your brain around more fuzz?

Monad satori eventually hits, the experts claim. Eventually, they promise. Don’t use analogies, they warn. Empty your mind. Contemplate the definition. It’s all about the laws!

Yadda big yadda.

You could buy into their skeezy cult. Or you could save yourself from all that bullshit by taking an email course spelling out Why Johnny Can’t Monad. And bonus: how to avoid the same fate—Because it isn’t Johnny’s fault, and you’ll find out why. The course is free!