Reader and Writer via Cont

We cannot easily produce a monad based on Cont that behaves exactly like Reader. This may be surprising at first, but it isn't if you think about it. Our implementation of the StateC monad isn't a proper state monad either, in the sense that it can do everything that the State monad can do, but it can do more! The State monad allows us to thread state through the computation, but it doesn't support callCC or any other shenanigans using continuations. Given that StateC is just Cont with a particular choice of the result type r', we have all the power of the Cont monad at our disposal.

When we introduced the Reader, State, and Writer monads, we talked about that technically, the State monad would be enough, because we can use State to implement any computation that uses the Reader monad, simply by using get in place of ask, and never using put, and similarly we could implement a version of tell on top of the State monad as

tell :: Monoid w => w -> State w ()
tell w = modify (<> w)

The reason why we wanted to have three distinct monads was that it better communicated our intent to the reader of our code. If we use the Reader monad, then we know that there is just no way that the computation modifies the read-only context. This makes it much easier to understand the code than if we have to trace all the state updates some code in the State monad performs.

By using Cont to implement State, we obtain a monad that supports all the operations that State supports, but it's a monad that can do more. Thus, we have already given up on using a monad that can do exactly what we need, nothing less but also nothing more. After all, we are in a fictitious world where we aren't allowed to define new monads. IO and Cont are the only monads we get. Our goal here is not to build specializations of Cont that behave exactly like other monads but to demonstrate that we can use Cont to do all those things we can do using other monads.¹

So, given that the Reader monad is nothing but a State monad that doesn't give us the ability to modify the state, we can define a Cont-based version exactly like our Cont-based state monad StateC. Only we don't provide an equivalent of put:

type ReaderC r s a = Cont (s -> r) a

ask :: ReaderC r s s
ask = Cont $ \k s -> k s s

runReader :: ReaderC r s r -> s -> r
runReader = runCont m id

Similarly, as we observed above, we can simulate the Writer monad as a State monad where the state is some monoid w, and we can implement tell by using modify to update the state. Thus, we can also obtain a version of Writer on top of Cont:

type WriterC r w a = Cont (w -> r) a

tell :: Monoid w => w -> WriterC r w ()
tell w = do
    w' <- get
    put (w' <> w)

runWriter :: Monoid w => WriterC (r, w) w a -> (r, w)
runWriter f = runCont f (,) mempty

Here, get and put are implemented as for the StateC monad. We can obtain a more direct implementation by reviewing what tell is supposed to do: It takes the current state w' and replaces it with w' <> w. The return value is (). Our implementation of such a function using the StateC monad would have been:

tell :: Monoid w => StateC r w a
tell w = Cont $ \k w' -> k () (w' <> w)

Since StateC r w a and WriterC r w a are defined identically, once we replace StateC with WriterC, we obtain a more efficient implementation of tell for the WriterC monad:

tell :: Monoid w => WriterC r w a
tell w = Cont $ \k w' -> k () (w' <> w)

Of course, this is a silly discussion to have in a sense because, if we really only want to be able to do what we can do using certain monads, then we don't need monads at all. We can just use pure functions. Remember, all monads other than IO and ST are just convenient abstractions implemented via pure functions. The point is that once we implement the right primitives, our implementations of the various monads on top of the Cont monad are just as convenient to use as the monads we're simulating. ↩