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
Is there a tutorial somewhere that picks this mumbo-jumbo apart and explains how and why this works? Not looking for a monad tutorial, but for a "how the Cont monad works" tutorial.
Here's another definition that may be easier to follow:
http://www.haskell.org/all_about_monads/html/contmonad.html#definition
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:
m, a value of type m a represents having access to a value of type a within the context of the monad.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.
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
Here's fibonacci:
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)
Imagine you have a machine without a call stack - it only allows tail recursion. How to execute fib 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 single call, which also has to give the result. Here's where continuations enter.
We'll make fib (n-1) take additional parameter, which will be a function specifying what should be done after computing the number x. It will be adding fib (n-2) to it, of course. So: to compute fib n you compute fib (n-1) after that, if you call the result x, you compute fib (n-2), after that, if you call the result y, you return x+y.
In other words you have to tell:
How to do the following computation: "fib' n c = compute fib n and apply c to the result"?
The answer is that you do the following: "compute fib (n-1) and apply d to the result", where d x means "compute fib (n-2) and apply e y to the result", where e y means c (x+y).
fib' 0 = \c -> c 0
fib' 1 = \c -> c 1
fib' n = \c -> fib' (n-1) $ \x ->
fib' (n-2) $ \y ->
c (x+y)
To get actual Fibonacci use identity: fib' n id.
The last three lines smell like a do block, and in fact
fib' 0 = return 0
fib' 1 = return 1
fib' n = do x <- fib' (n-1)
y <- fib' (n-2)
return (x+y)
is the same, up to newtypes, by definition of monad Cont. Note differences. There's \c -> at the beginning, instead of x <- ... there's ... $ \x -> and c instead of return.
Try writing factorial 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 in fib', you get
\c -> m $ \a ->
k a $ \t ->
c t
simplifying \t -> c t to c
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 between do 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 is Cont (m b) a. See sigfpe's Mother 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.