One Monad to Rule Them All

Let's recap what we have learned about continuations so far: Programming in continuation passing style turns functions "inside out". Instead of returning a value, a function in CPS expects a function as argument, which it calls in tail position using the value a normal function would have returned as argument. By calling this function in tail position, it uses it as a continuation. The only thing a normal function can do is to return a value. It has no control over what happens to this value after it returns. When programming in CPS, we can provide a function with multiple possible continuations, and the function can choose between them, thereby exerting explicit control over what happens once it "returns". That's pretty much exactly what the yield function constructed by callCC did. One of its arguments is the continuation that represents the computation after yield returns. But yield also has access to the continuation that represents the computation after callCC returns. yield never calls the "normal" continuation and always calls the continuation after callCC. By doing so, yield effectively never returns, and it makes callCC return immediately even if we call yield from inside some deeply nested context.

This explicit control over the future of a computation after a function returns is what makes CPS an extremely powerful tool. Unfortunately, even doing easy things in CPS feels much less natural than working with normal functions, and if we do really complex things in CPS, we are almost guaranteed to write code that nobody, even our future self, has no way to understand. The Cont monad, and its transformer version ContT, brought some sanity back, by doing all the passing around of continuations for us, behind the scenes of do-notation. Thus, we can mostly forget that we're programming in CPS, but we do gain the power of programming in CPS when we need to by using callCC.

To further demonstrate the power of the Cont monad, let's ask a provocative question. Assume that Haskell didn't give us the ability to define our own monads. The only thing the implementers of Haskell are willing to do is to give us one monad they're willing to build right into the language. Which one would we choose?

Actually, the answer should immediately be, "the IO monad," because we cannot do anything useful if we cannot perform I/O. Okay, then let's assume that we're allowed to have two monads. One of them must be IO because we cannot do anything without it. What should the other one be? Clearly, State, Reader, Writer, Maybe, the list monad, and Cont are all useful for certain types of programs. Can we really choose one over all the others?

Yes. We should choose Cont over all the others, because many other monads can be simulated using Cont, simply by choosing the return type r in Cont r appropriately. Let's look at a few examples.