Permalink
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
229 lines (176 sloc) 7.92 KB
---
title: "The Update Monad"
date: 2018-07-26T22:48:10BST
---
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](https://danelahman.github.io/papers/types13postproc.pdf). 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](https://github.com/hashanp/hashanp.xyz/tree/master/content/posts/update.lhs), and run the file. The Haskell code in this post is going to need the following language extensions and imports:
\begin{code}
{-# LANGUAGE InstanceSigs #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE FlexibleInstances #-}
import Data.Monoid ((<>))
\end{code}
Let's recap the reader and writer monads. The reader monad can be defined as follows:
\begin{code}
newtype Reader m r = Reader { runReader :: (m -> r) }
\end{code}
The writer monad can be defined as follows:
\begin{code}
newtype Writer m r = Writer { runWriter :: (r, m) } deriving (Show)
\end{code}
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:
\begin{code}
instance Functor (Reader m) where
fmap :: (r -> r') -> Reader m r -> Reader m r'
fmap f (Reader t) = Reader (f . t)
instance Functor (Writer m) where
fmap :: (r -> r') -> Writer m r -> Writer m r'
fmap f (Writer (r, m)) = Writer (f r, m)
\end{code}
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:
\begin{code}
instance Applicative (Reader m) where
pure :: r -> Reader m r
pure x = Reader (\_ -> x)
(<*>) :: Reader m (a -> b) -> Reader m a -> Reader m b
(Reader f) <*> (Reader m) = Reader (\x -> (f x (m 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')
\end{code}
Finally let's write the monad instances:
\begin{code}
instance Monad (Reader m) where
(>>=) :: Reader m r -> (r -> Reader m r') -> Reader m r'
(Reader t) >>= f = Reader (\x -> runReader (f (t x)) x)
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
\end{code}
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`:
\begin{code}
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
\end{code}
The state monad follows straightforwardly from these two monads:
\begin{code}
type State m s = Reader m (Writer m s)
\end{code}
The monad reads an initial state, and returns the new state. Alternatively it could be defined as follows:
\begin{code}
newtype State' m s = State' { runState' :: (m -> (s, m)) }
\end{code}
Let's write the functor, applicative and monad instances for `State`:
\begin{code}
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
\end{code}
An example of where a state monad would be useful is with a stack:
\begin{code}
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
\end{code}
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:
\begin{code}
class (Monoid m) => MonoidAction m s where
act :: m -> s -> s
\end{code}
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:
\begin{code}
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'
\end{code}
Finally, let's write the code for the update monad:
\begin{code}
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
\end{code}
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:
```haskell
runUpdate test' [1, 2, 3]
```
Would produce:
```haskell
([4,1,2,3], [Push 4, Push 7, Push 9, Pop, Pop])
```