Skip to content

The Cont Monad

In the previous section, we observed that a value of type a and a function of type (a -> r) -> r represent the same information. That was the key to programming in CPS. Let's wrap the latter in a newtype, as we always do when we want to build a new monad:

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

To turn this into a monad, we first need to make it a functor. Given a function f :: a -> b, we should be able to apply this to a value of type Cont r a to obtain a value of type Cont r b:

instance Functor (Cont r) where
    fmap f (Cont contA) = Cont $ \fbr -> ...

The ... should produce a value of type r. What we have at our disposal are

fbr   :: b -> r
f     :: a -> b
contA :: (a -> r) -> r

Of these, only fbr and contA produce values of type r. To use fbr, we need to provide it with a value of type b. The only function we have that produces a value of type b is f. So we build the function composition fbr . f :: a -> r. Now we would need a value of type a to which to apply fbr . f, but we have no function anywhere that produces a value of type a. What we do have is the next best thing: a function contA that turns a function of type a -> r, such as fbr . f, into a value of type r. So that's our implementation of fmap:

instance Functor (Cont r) where
    fmap f (Cont contA) = Cont $ \fbr -> contA (fbr . f)

I encourage you to verify that this implementation satisfies the functor laws.

Next let's implement a Monad instance for Cont r. return should take a value x :: a and turn into a value of type Cont r a that represents x. Now observe that Cont r a is simply a wrapper around the type (a -> r) -> r. We already figured out before how to turn a value of type a into a function of this type that represents this value:

toCPS :: a -> ((a -> r) -> r)
toCPS x = ($ x)

All that return has to do is to wrap this function in Cont. Thus,

return x = Cont ($ x)

(>>=) is where things get interesting. Let's recall what x >>= f is supposed to do. It is supposed to apply the function f to x. This would be easy if x had the type a an f had the type a -> b, but now we have x :: Cont r a and f :: a -> Cont r b. Thus, we somehow need extract the value that x contains. Let's try this without the Cont wrappers, because this should seem familiar by now. In this case, we have x :: ((a -> r) -> r) and f :: a -> (b -> r) -> r, and we want that x >>= f :: (b -> r) -> r. Here's a first attempt that doesn't quite work, even though it captures the correct spirit:

x >>= f = x $ \a -> f a

or, without the unneccessary anonymous function,

x >>= f = x f

That's standard CPS. Instead of applying f to x, we pass a continuation to x. This continuation captures the value a represented by x as its argument and then invokes f on a. Why doesn't this work? Note that our monad here is Cont r. This means that the return type r is fixed. Since x :: Cont r a and f :: a -> Cont r b, the functions wrapped by x and by f a must have the same return type. But that's not the case in the implementation we chose.

The continuation we pass to x is f, which has the type a -> (b -> r) -> r. x has the type ((a -> r') -> r'). To be able to pass f to x as an argument, thus need to choose r' = (b -> r) -> r, but this is obviously a different type from r.

We can fix this by being more explicit in how we unpack and repack values in our implementation. Let's build it up slowly. We want x >>= f to have the type (b -> r) -> r, so it takes as argument a function fbr :: b -> r.

x >>= f = \fbr -> ...

The ... should become a value of type r. What we have at our disposal is

x   :: (a -> r) -> r
f   :: a -> (b -> r) -> r
fbr :: b -> r

Each of these functions is a candidate that we might use to produce a value of type r. Upon closer inspection, fbr is out because none of the functions we have allows us to produce a value of type b to which we might apply fbr. Let's try f. We can use it to build a function of type a -> r:

\a -> f a fbr

We can't use this function directly to produce a value of type r either, because we have no way to produce a value of type a. But x can produce a value of type r if we provide it with a function of type a -> r, and that's exactly the type of \a -> f a fbr. Thus, we have

x >>= f = \fbr -> x $ \a -> f a fbr

It takes some squinting to see how this is function application. It's just CPS again. We represent the return value y of x >>= f as a function that applies a continuation fbr to y. This return value y of x >>= f is produced by f but not directly. f produces its value as a function that accepts a continuation which it then applies to y. So we pass our continuation fbr to f a. Now, we also don't have direct access to the value a to which we want to apply f. x represents this value in the form of a function that accepts a continuation of type a -> r. So we build such a continuation, and this continuation calls f a fbr.

All that remains is to add the correct code to remove and add the correct Cont wrappers:

x >>= f = Cont $ \fbr -> runCont x $ \a -> runCont (f a) fbr

The whole Monad instance is:

instance Monad (Cont r) where
    return x = Cont ($ x)
    x >>= f  = Cont $ \fbr -> runCont x $ \a -> runCont (f a) fbr

As always, this is how we like to think about the Cont monad, but it is once again useful if we can equip other monads with continuations, so what we have is in fact a monad transformer

newtype ContT r m a = ContT { runContT :: (a -> m r) -> m r }

and Cont r is defined by choosing m = Identity:

type Cont r a = ContT r Identity a

runCont :: Cont r a -> (a -> r) -> r
runCont x f = runIdentity $ runContT x (Identity . f)

Interestingly, for ContT r m to be a monad, we don't even need m to be a monad itself, as was required for StateT s m, WriterT w m, ReaderT r m or MaybeT m to be a monad. The reason is that the Monad instances for the latter four monads rely on the (>>=) operator of m for their implementation. The following implementation of a Monad instance for ContT r m does not do this. It is in fact exactly the same as the monad instance for Cont r:

instance Monad (ContT r m) where
    return x = ContT ($ x)
    x >>= f  = ContT $ \fbr -> runContT x $ \a -> runConT (f a) fbr

If you're surprised by this, note the following fundamental difference between ContT r m a and, say Reader r m a. The latter wraps a function of type r -> m a. The return value a is decorated with the monad m. ContT r m a wraps a function of type (a -> m r) -> m r. We should still think about a as the return type of this computation. In the type (a -> m r) -> m r, this type is just as unadorned as in the function type (a -> r) -> r that is wrapped by Cont r a. Indeed, we can think about ContT r m a as being the same as Cont (m r) a.

Let's take stock what we have achieved so far. Using the Cont monad, we can now implement our facCPS function much more naturally:

facCPS :: Integer -> Cont r Integer
facCPS 0 = return 0
facCPS n = do
    f <- facCPS (n - 1)
    return (n * f)

Apart from the use of do-notation and return, this looks like ordinary code that involves no continuations. Under the hood, it's all continuations though. The Cont monad lets us forget it all:

GHCi
>>> import Control.Monad.Cont
>>> :{
  | facCPS :: Integer -> Cont r Integer
  | facCPS 0 = return 1
  | facCPS n = do
  |     f <- facCPS (n - 1)
  |     return (n * f)
  | :}
>>> runCont (facCPS 10) id
3628800

We can also easily compute a double factorial as before. Again, there is no explicit manipulations of continuations anymore:

GHCi
>>> runCont (facCPS 4 >>= facCPS) id
620448401733239439360000

And our example of computing \(3! + 4! + 5!\) also looks rather natural now:

GHCi
>>> :{
  | flip runCont id $ do
  |     f3 <- facCPS 3
  |     f4 <- facCPS 4
  |     f5 <- facCPS 5
  |     return (f3 + f4 + f5)
  | :}
150

This restores sanity, but it is also less than exciting. We could do all of this using pure functions without using a monad. What we have lost for the moment is the ability to use continuations explicitly to implement interesting things such as exception handling and coroutines. That's no different than what we encountered for the Reader, Writer, and State monads: When using do-notation, the decoration of the monad is hidden from us. For Reader, Writer, and State, we had functions ask, tell, get, and put that allowed us to access the context, log or state from within do-blocks. We need something similar for our Cont monad, a function that lets us access the current continuation. Unsurprisingly this function is called "call with current continuation" or callCC, in analogy to call/cc in Scheme. We're going to look at callCC next.