I had trouble using the continuation monad until I understood how it works. Here is what I wish I knew from the beginning. The examples are written in PureScript.
What is a continuation?
A continuation is the next step in a computation. Consider this expression:
We start by evaluating the sub-expression
2 / 2.
Let’s replace it with a placeholder for the value of that expression.
The continuation is everything surrounding the placeholder. We can think of the continuation as a function. Calling the function completes the computation.
There is always a next step, another continuation, until the computation is finished. But these steps are not something that you, the programmer, can always manipulate. Constructs like if/else and try/catch give you some control over the next step. The continuation pattern gives you full control.
What is continuation-passing style?
Continuation-passing style (CPS) is contrasted with direct style. A function written in direct style takes some arguments and returns a value. Returning a value advances the computation to the next step.
Here is the last expression translated to direct style.
A CPS function takes an additional argument, a continuation. Instead of returning a value, it calls the continuation.
Here is the last example written in continuation-passing style.
add are called, a continuation is passed forward.
The continuation is called with a value that is used to do the next step of the
What is the ContT type?
Let’s look at the types of the above functions.
r is the result of calling the continuation.
We can think of these functions not as returning an
r but as returning a
That way of thinking is the basis for the
ContT wraps a function that takes a continuation
a -> m r and returns any
r in a functor
Functions written in a continuation-passing style pass the continuation around
The use of
runContT above is an awkward imitation of that style.
We’d rather compose each step and then run them all together.
How does ContT compose?
Each step in our example depends on the result of the previous step.
The previous step passes its result to the next step through a continuation.
We’re looking for a way to combine steps without having to run
Let’s call this operator
We can generalize
andThen to this type.
Now we can see that
ContT will enable us to perform steps sequentially without
so much plumbing.
How is bind defined for ContT
The arguments to
bind seem like they should connect but it wasn’t
immediately obvious to me how they could.
Start by destructuring
We have these functions in scope.
And we want to return a value of this type.
If we had access to an
a, it would be easy.
We could just apply
But we don’t have direct access to an
The only place we find
a as an input is the continuation of
To gain access to
a, we must supply that continuation.
Now we can apply
But this doesn’t compile.
The types are wrong.
The continuation must be a function
a -> m r.
And we’ve supplied a function
a -> ContT r m b.
We can try to fix this problem by running the result of
There are two problems.
First, we must supply a continuation
b -> m r to
runContT but we don’t have
a value of that type in scope.
bindContT now returns
m r but it should return
Cont r m b.
Both problems are fixed in the same way, by wrapping everything in another continuation-passing style function.
Here is what happens:
mperforms the first step, e.g.
div 2 2
- The continuation of
mperforms the second step, e.g.
mult 3 1
- This is all wrapped in a CPS function with a continuation
- The third step is performed by
add 1 3
Ergonomic composition of CPS functions
Thus, the continuation monad enables us to perform steps sequentially without threading the continuation explicitly.