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:
{-# LANGUAGE InstanceSigs #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE FlexibleInstances #-}

import Data.Monoid ((<>))

newtype Reader m r = Reader { runReader :: (m -> r) }

The writer monad can be defined as follows:

newtype Writer m r = Writer { runWriter :: (r, m) } deriving (Show)

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:

instance Functor (Reader m) where
fmap :: (r -> r') -> Reader m r -> Reader m r'

instance Functor (Writer m) where
fmap :: (r -> r') -> Writer m r -> Writer m r'
fmap f (Writer (r, m)) = Writer (f r, m)

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:

instance Applicative (Reader m) where
pure :: r -> Reader m r
pure x = Reader (\_ -> x)

instance (Monoid m) => Applicative (Writer m) where
pure :: r -> Writer m r
pure x = Writer (x, mempty)
(<*>) :: Writer m (a -> b) -> Writer m a -> Writer m b
(Writer (r, m)) <*> (Writer (r', m')) = Writer (r r', m <> m')

Finally let’s write the monad instances:

instance Monad (Reader m) where

return = pure

instance (Monoid m) => Monad (Writer m) where
(>>=) :: Writer m r -> (r -> Writer m r') -> Writer m r'
(Writer (r, m)) >>= f = Writer (r', m <> m')
where (r', m') = runWriter (f r)

return = pure

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:

log' :: m -> Writer [m] ()
log' m = Writer ((), [m])

factorial :: Int -> Writer [String] Int
factorial n =
if n == 0
then return 1
else do
log' $"Multiplying " ++ (show n) subproblem <- factorial (n - 1) return$ n * subproblem
type State m s = Reader m (Writer m s)
The monad reads an initial state, and returns the new state. Alternatively it could be defined as follows:
newtype State' m s = State' { runState' :: (m -> (s, m)) }

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

instance Functor (State' m) where
fmap :: (a -> b) -> (State' m a) -> (State' m b)
fmap f t = State' t'
where t' x = (f s, m)
where (s, m) = runState' t x

instance Applicative (State' m) where
pure :: a -> State' m a
pure x = State' $\m -> (x, m) (<*>) :: State' m (a -> b) -> State' m a -> State' m b f <*> a = State' b where b x = (s s', m') where (s', m') = runState' a x (s, m) = (runState' f m) instance Monad (State' m) where (>>=) :: State' m a -> (a -> State' m b) -> State' m b a >>= f = State' b where b x = (s', m') where (s, m) = runState' a x (s', m') = runState' (f s) m return = pure An example of where a state monad would be useful is with a stack: push :: a -> State' [a] () push x = State'$ \xs -> ((), x:xs)

pop :: State' [a] a
pop = State' $\(x:xs) -> (x, xs) test :: State' [Int] Int test = do push 4 push 6 push 7 push 9 pop pop 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: class (Monoid m) => MonoidAction m s where act :: m -> s -> s 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: data Op = Push Int | Pop deriving (Show) instance MonoidAction [Op] [Int] where act [] = id act (Pop:xs) = \(v:vs) -> act xs vs act (Push v:xs) = \vs -> act xs (v:vs) push' :: Int -> Update [Op] [Int] () push' m = Update$ \_ -> ((), [Push m])

pop' :: Update [Op] [Int] Int
pop' = Update $\(x:_) -> (x, [Pop]) read' :: Update [Op] [Int] [Int] read' = Update$ \xs -> (xs, [])

test' :: Update [Op] [Int] [Int]
test' = do
push' 4
push' 7
push' 9
pop'
pop'
read'

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

newtype Update a s m = Update { runUpdate :: s -> (m, a) }

instance Functor (Update a s) where
fmap :: (c -> d) -> Update a s c -> Update a s d
fmap f u = Update u'
where u' s = (f m, a)
where (m, a) = runUpdate u s

instance (MonoidAction a s) => Applicative (Update a s) where
pure :: m -> Update a s m
pure x = Update \$ \_ -> (x, mempty)

(<*>) :: Update a s (c -> d) -> Update a s c -> Update a s d
f <*> c = Update u
where u s = (m m', a <> a')
where (m, a) = runUpdate f s
(m', a') = runUpdate c (act a s)

instance (MonoidAction a s) => Monad (Update a s) where
(>>=) :: Update a s c -> (c -> Update a s d) -> Update a s d
f >>= c = Update u
where u s = (m', a <> a')
where (m, a) = runUpdate f s
(m', a') = runUpdate (c m) (act a s)

return = pure

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:

runUpdate test' [1, 2, 3]

Would produce:

([4,1,2,3], [Push 4, Push 7, Push 9, Pop, Pop])