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

The basic idea of a continuation in general is that it representsthe 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 ispart of the total expression, but it's not just a function we can apply. Instead, it's something we need to apply a functionto. So, we can talk about the "rest of the computation" in this case as being\a -> foo a z, which we can apply tobar 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 usmanipulate that outer context within the subexpression itself. We can think of it asa 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 thanfunction application, reversed. We could just as easily writeflip ($), 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 thinkbuilding a computation within a background context the next thing we think issay, is this a monad? And in this case the answer isyes, yes it is.

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

• For a monadm, a value of typem a represents having access to a value of typea 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 typea within this context? It just means that, for some valuex :: a, we've appliedflip ($) tox, giving us a function that takes a function which takes an argument of typea, and applies that function tox. Let's say we have a suspended computation holding a value of typeBool. What type does this give us?

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

So for suspended computations, the typem a works out to(a -> b) -> b... which is perhaps an anticlimax, since we already knew the signature forCont, 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 functiona -> b and evaluates tob. As a continuation represents "the future" of a computation, so the typea in the signature represents in some sense "the past".

So, replacing(a -> b) -> b withCont b a, what's the monadic type for our basic building block of reverse function application?a -> (a -> b) -> b translates toa -> Cont b a... the same type signature asreturn 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 actuallydoing?

At this point we come back to what I said initially: the continuation monad isn't reallydoing much of anything. Something of typeCont r a is trivially equivalent to something of just typea, simply by supplyingid as the argument to the suspended computation. This might lead one to ask whether, ifCont r a is a monad but the conversion is so trivial, shouldn'ta alonealso be a monad? Of course that doesn't work as is, since there's no type constructor to define as aMonad instance, but say we add a trivial wrapper, likedata Id a = Id a. This isindeed a monad, namely the identity monad.

What does>>= do for the identity monad? The type signature isId a -> (a -> Id b) -> Id b, which is equivalent toa -> (a -> b) -> b, which is just simple function application again. Having established thatCont r a is trivially equivalent toId 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, thereisn't actually anything unusual going on! Applying functions to arguments, ho hum, another day in the life of a functional programmer.

Here's fibonacci:

fib 0 = 0fib 1 = 1fib n = fib (n-1) + fib (n-2)

Imagine you have a machine without a call stack - it only allows tail recursion. How to executefib on that machine? You could easily rewrite the function to work in linear, instead of exponential time, but that requires tiny bit of insight and is not mechanical.

The obstacle to making it tail recursive is the third line, where there are two recursive calls. We can only make a single call, which also has to give the result. Here's where continuations enter.

We'll makefib (n-1) take additional parameter, which will be a function specifying what should be done after computing its result, call itx. It will be addingfib (n-2) to it, of course. So: to computefib n you computefib (n-1) after that, if you call the resultx, you computefib (n-2), after that, if you call the resulty, you returnx+y.

In other words you have to tell:

How to do the following computation: "fib' n c = computefib n and applyc to the result"?

The answer is that you do the following: "computefib (n-1) and applyd to the result", whered x means "computefib (n-2) and applye to the result", wheree y meansc (x+y). In code:

fib' 0 c = c 0fib' 1 c = c 1fib' n c = fib' (n-1) d           where d x = fib' (n-2) e                 where e y = c (x+y)

Equivalently, we can use lambdas:

fib' 0 = \c -> c 0fib' 1 = \c -> c 1fib' n = \c -> fib' (n-1) $ \x ->               fib' (n-2) $ \y ->               c (x+y)

To get actual Fibonacci use identity:fib' n id. You can think that the linefib (n-1) $ ... passes its resultx to the next one.

The last three lines smell like ado block, and in fact

fib' 0 = return 0fib' 1 = return 1fib' n = do x <- fib' (n-1)            y <- fib' (n-2)            return (x+y)

is the same, up to newtypes, by definition of monadCont. Note differences. There's\c -> at the beginning, instead ofx <- ... there's... $ \x -> andc instead ofreturn.

Try writingfactorial n = n * factorial (n-1) in a tail recursive style using CPS.

How does>>= work?m >>= k is equivalent to

do a <- m   t <- k a   return t

Making the translation back, in the same style as infib', you get

\c -> m $ \a ->      k a $ \t ->      c t

simplifying\t -> c t toc

m >>= k = \c -> m $ \a -> k a c

Adding newtypes you get

m >>= k  = Cont $ \c -> runCont m $ \a -> runCont (k a) c

which is on top of this page. It's complex, but if you know how to translate betweendo notation and direct use, you don't need to know exact definition of>>=! Continuation monad is much clearer if you look at do-blocks.

Monads and continuations

If you look at this usage of list monad...

do x <- [10, 20]   y <- [3,5]   return (x+y)[10,20] >>= \x ->  [3,5] >>= \y ->    return (x+y)([10,20] >>=) $ \x ->  ([3,5] >>=) $ \y ->    return (x+y)

that looks like continuation! In fact,(>>=) when you apply one argument has type(a -> m b) -> m b which isCont (m b) a. See sigfpe'sMother of all monads for explanation. I'd regard that as a good continuation monad tutorial, though it wasn't probably meant as it.

Since continuations and monads are so strongly related in both directions, I think what applies to monads applies to continuations: only hard work will teach you them, and not reading some burrito metaphor or analogy.

EDIT: Article migrated to the link below.

I've written up a tutorial directly addressing this topic that I hope you will find useful. (It certainly helped cement my understanding!) It's a bit too long to fit comfortably in a Stack Overflow topic, so I've migrated it to the Haskell Wiki.

Please see:MonadCont under the hood

I think the easiest way to get a grip on theCont monad is to understand how to use its constructor. I'm going to assume the following definition for now, although the realities of thetransformers package are slightly different:

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

This gives:

Cont :: ((a -> r) -> r) -> Cont r a

so to build a value of typeCont r a, we need to give a function toCont:

value = Cont $ \k -> ...

Now,k itself has typea -> r, and the body of the lambda needs to have typer. An obvious thing to do would be to applyk to a value of typea, and get a value of typer. We can do that, yes, but that's really only one of many things we can do. Remember thatvalue need not be polymorphic inr, it might be of typeCont String Integer or something else concrete. So:

• We could applyk to several values of typea, and combine the results somehow.
• We could applyk to a value of typea, observe the result, and then decide to applyk to something else based on that.
• We could ignorek altogether and just produce a value of typer ourselves.

But what does all this mean? What doesk end up being? Well, in a do-block, we might have something looking like this:

flip runCont id $ do  v <- thing1  thing2 v  x <- Cont $ \k -> ...  thing3 x  thing4

Here's the fun part: we can, in our minds and somewhat informally, split the do-block in two at the occurrence of theCont constructor, and think of the rest of the entire computationafter it as a value in itself. But hold on, what it is depends on whatx is, so it's really afunction from a valuex of typea to some result value:

restOfTheComputation x = do  thing3 x  thing4

In fact, thisrestOfTheComputation isroughly speaking whatk ends up being. In other words, you callk with a value which becomes the resultx of yourCont computation, the rest of the computation runs, and then ther produced winds its way back into your lambda as the result of the call tok. So:

• if you calledk multiple times, the rest of the computation will get run multiple times, and the results may be combined however you wish.
• if you didn't callk at all, the rest of the entire computation will be skipped, and the enclosingrunCont call will just give you back whatever value of typer you managed to synthesise. That is, unless some other part of the computation is callingyou fromtheirk, and messing about with the result...

If you're still with me at this point it should be easy to see this could be quite powerful. To make the point a little, let's implement some standard type classes.

instance Functor (Cont r) where  fmap f (Cont c) = Cont $ \k -> ...

We're given aCont value with bind resultx of typea, and a functionf :: a -> b, and we want to make aCont value with bind resultf x of typeb. Well, to set the bind result, just callk...

  fmap f (Cont c) = Cont $ \k -> k (f ...

Wait, where do we getx from? Well, it's going to involvec, which we haven't used yet. Remember howc works: it gets given a function, and then calls that function with its bind result. We want to callour function withf applied to that bind result. So:

  fmap f (Cont c) = Cont $ \k -> c (\x -> k (f x))

Tada! Next up,Applicative:

instance Applicative (Cont r) where  pure x = Cont $ \k -> ...

This one's simple. We want the bind result to be thex we get.

  pure x = Cont $ \k -> k x

Now,<*>:

  Cont cf <*> Cont cx = Cont $ \k -> ...

This a little trickier, but uses essentially the same ideas as in fmap: first get the function from the firstCont, by making a lambda for it to call:

  Cont cf <*> Cont cx = Cont $ \k -> cf (\fn -> ...

Then get the valuex from the second, and makefn x the bind result:

  Cont cf <*> Cont cx = Cont $ \k -> cf (\fn -> cx (\x -> k (fn x)))

Monad is much the same, although requiresrunCont or a case or let to unpack the newtype.

This answer is already quite long, so I won't go intoContT (in short: it is exactly the same asCont! The only difference is in the kind of the type constructor, the implementations of everything are identical) orcallCC (a useful combinator that provides a convenient way to ignorek, implementing early exit from a sub-block).

For a simple and plausible application, try Edward Z. Yang's blog post implementinglabelled break and continue in for loops.

• haskell
• monads
• continuations