The Update Monad

Published on the

Last night, I attended a talk at the London Haskell meetup, by Gabe Dijkstra, on the topic of the Update Monad. Admittedly, the finer theoretical details were a little over my head, but after a lot of thinking I was finally able to get my head round the concept. This post, will only look at the topic from a practical perspective, with an implementation in Haskell.

The update monad was devised in the paper Update Monads: Cointerpreting Directed Containers. You can find it here. It’s presented as a generalisation of the reader and writer monads. Some readers might know that the state monad is also a generalisation of these two monads. In fact that state monad can be represented using the update monad.

Note that this post is written as a literate Haskell file, so you can download the post from here, and run the file. The Haskell code in this post is going to need the following language extensions and imports:

Let’s recap the reader and writer monads. The reader monad can be defined as follows:

The writer monad can be defined as follows:

Remember m is the type of the data read/written, whereas r is the type of the data “contained”.

The functor laws can be easily defined:

Note since functions are already functors, we could also have written fmap f t, in the case of Reader. Now let’s write the applicative instances:

Finally let’s write the monad instances:

An example of a reader monad is when dealing with functions that read from some sort of configuration. In this case, you’d want the configuration to be “passed along”. An example of a writer monad is when dealing with functions which may need to log output. E.g. to report errors or warnings. For the writer to have instances of applicative and monad, the “log” type must be a monoid. This means the logs produced by two different functions can be composed nicely. Here’s an example of Writer:

The state monad follows straightforwardly from these two monads: The monad reads an initial state, and returns the new state. Alternatively it could be defined as follows:

Let’s write the functor, applicative and monad instances for State:

An example of where a state monad would be useful is with a stack:

The update monad composes the reader and writer monad in alternative way. Rather than returning a secondary value, representing the new state, the update releases a secondary value representing actions, or updates, to be performed onto the state. The key thing is that these actions are composable. They are in fact, monoid actions. You can get the relevant typeclass from the monoid-extras package, but I’m going to define it here for completeness:

There are two laws that should be obeyed. Firstly act mempty = id. Secondly act (x <> y) = act y . act x. Observe that the first parameter of act is the action, and the second is value that receives the update. The value returned is the result of the value being applied the action.

Consider how this could be applied to the example of a stack:

Finally, let’s write the code for the update monad:

Note again, the key thing is that the internal state is modified through a clean interface of actions, and the history of how the state is changed is preserved.

Running the following:

Would produce: