Skip to content

Continuations in Haskell

Now let's translate this all into Haskell. How could we model continuations using pure functions? Here's the crux:

A continuation is nothing but a function!

Remember, in Scheme, we called a continuation, possibly with some argument, and that continued the computation from the moment when call/cc returns. Since Haskell is a statically typed language, we need to specify the type of the result produced by this computation after call/cc returns. Let's call this type r (for "result"). If our continuation takes an argument, we also need to specify the type of this argument. Let's call it a. This makes a continuation into a function of type a -> r.

The use of continuations in Scheme is a bit magical1. If a function f invokes some closure g, then the remainder of the computation that f would have carried out had it not invoked g is aborted. We replace f's future with the computation captured by g. You may have to squint quite hard to see this, but that's an idea we are already familiar with: If f calls g in tail position, then f does nothing else after the call to g returns. In effect, g becomes the future of the computation from the time when f invokes g.

A function becomes a continuation by virtue of being called in tail position.

In Scheme, if we have a function foo that should have the ability to abort its computation by invoking an invocation, we need to call foo with this continuation as argument. foo can then terminate normally, without ever invoking the continuation, or it may invoke the computation and abort the rest of its computation. Since continuations in Haskell are plain functions of some type a -> r, the type of foo in Haskell would simply be

foo :: (a -> r) -> r

No matter whether it invokes the continuation, the result of foo needs to have the same type r. The invocation foo cont may compute its result of type r without ever calling cont—just as the Scheme function may never invoke the continuation it is given—or it may call cont in tail position to produce the final result.

Note that there is nothing that prevents foo from calling cont and then performing additional steps after cont returns. In that case, foo uses cont as a normal function, not as a continuation. Read the sentence above once more: A function (of type a -> r) becomes a continuation by virtue of being called in tail position.

Another important point we should make is that there is nothing that prevents us from defining a function that takes more than one continuation as argument and then chooses between the two to produce its result:

evenOrOdd :: Int -> (Int -> r) -> (Int -> r) -> r
evenOrOdd x whenEven whenOdd
    | even x    = whenEven x
    | otherwise = whenOdd  x

Here, we have two continuations whenEven and whenOdd that both can be used to produce a value of type r, and we invoke each depending on whether x is even or odd.

GHCi
>>> :{
  | evenOdd x whenEven whenOdd
  |     | even x    = whenEven x
  |     | otherwise = whenOdd  x
  | :}
>>> roundDown x = evenOdd x id (subtract 1)
>>> roundDown 2
2
>>> roundDown 5
4

  1. Continuations are implemented directly in Scheme's runtime system. This implementation turns out to be fairly easy in fact, given that Scheme doesn't really have stack frames and instead stores closures on the heap. Each closure has a pointer to the closure from which it was invoked. The chain of these pointers reflects the history of function calls that got us to the point captured by this closure. A continuation object does little more than hold on to such a closure. By invoking the continuation, we return to the state captured by this closure, including the sequence of function calls that got us to this closure. This is whan enables function calls to return more than once if we use a continuation to jump back into a function from which we have returned before. ↩