How and why does the Haskell Cont monad work?

Question

This is how the Cont monad is defined:

newtype Cont r a = Cont { runCont :: (a -> r) -> r }

instance Monad (Cont r) where
    return a = Cont ($ a)
    m >>= k  = Cont $ \c -> runCont m $ \a -> runCont (k a) c

Could you explain how and why this works? What is it doing?

Answer 1

The first thing to realize about the continuation monad is that, fundamentally, it's not really doing anything at all. It's true!

The basic idea of a continuation in general is that it represents the rest of a computation. Say we have an expression like this: foo (bar x y) z. Now, extract just the parenthesized portion, bar x y--this is part of the total expression, but it's not just a function we can apply. Instead, it's something we need to apply a function to. So, we can talk about the "rest of the computation" in this case as being \a -> foo a z, which we can apply to bar x y to reconstruct the complete form.

Now, it happens that this concept of "the rest of the computation" is useful, but it's awkward to work with, since it's something outside of the subexpression we're considering. To make things work better, we can turn things inside-out: extract the subexpression we're interested in, then wrap it in a function that takes an argument representing the rest of the computation: \k -> k (bar x y).

This modified version gives us a lot of flexibility--not only does it extract a subexpression from its context, but it lets us manipulate that outer context within the subexpression itself. We can think of it as a sort of suspended computation, giving us explicit control over what happens next. Now, how could we generalize this? Well, the subexpression is pretty much unchanged, so let's just replace it with a parameter to the inside-out function, giving us \x k -> k x--in other words, nothing more than function application, reversed. We could just as easily write flip ($), or add a bit of an exotic foreign language flavor and define it as an operator |>.

Now, it would be simple, albeit tedious and horribly obfuscating, to translate every piece of an expression to this form. Fortunately, there's a better way. As Haskell programmers, when we think building a computation within a background context the next thing we think is say, is this a monad? And in this case the answer is yes, yes it is.

To turn this into a monad, we start with two basic building blocks:

• For a monad m, a value of type m a represents having access to a value of type a within the context of the monad.
• The core of our "suspended computations" is flipped function application.

What does it mean to have access to something of type a within this context? It just means that, for some value x :: a, we've applied flip ($) to x, giving us a function that takes a function which takes an argument of type a, and applies that function to x. Let's say we have a suspended computation holding a value of type Bool. What type does this give us?

> :t flip ($) True
flip ($) True :: (Bool -> b) -> b

So for suspended computations, the type m a works out to (a -> b) -> b... which is perhaps an anticlimax, since we already knew the signature for Cont, but humor me for now.

An interesting thing to note here is that a sort of "reversal" also applies to the monad's type: Cont b a represents a function that takes a function a -> b and evaluates to b. As a continuation represents "the future" of a computation, so the type a in the signature represents in some sense "the past".

So, replacing (a -> b) -> b with Cont b a, what's the monadic type for our basic building block of reverse function application? a -> (a -> b) -> b translates to a -> Cont b a... the same type signature as return and, in fact, that's exactly what it is.

From here on out, everything pretty much falls directly out from the types: There's essentially no sensible way to implement >>= besides the actual implementation. But what is it actually doing?

At this point we come back to what I said initially: the continuation monad isn't really doing much of anything. Something of type Cont r a is trivially equivalent to something of just type a, simply by supplying id as the argument to the suspended computation. This might lead one to ask whether, if Cont r a is a monad but the conversion is so trivial, shouldn't a alone also be a monad? Of course that doesn't work as is, since there's no type constructor to define as a Monad instance, but say we add a trivial wrapper, like data Id a = Id a. This is indeed a monad, namely the identity monad.

What does >>= do for the identity monad? The type signature is Id a -> (a -> Id b) -> Id b, which is equivalent to a -> (a -> b) -> b, which is just simple function application again. Having established that Cont r a is trivially equivalent to Id a, we can deduce that in this case as well, (>>=) is just function application.

Of course, Cont r a is a crazy inverted world where everyone has goatees, so what actually happens involves shuffling things around in confusing ways in order to chain two suspended computations together into a new suspended computation, but in essence, there isn't actually anything unusual going on! Applying functions to arguments, ho hum, another day in the life of a functional programmer.