Emanuele Balboni
Una monade simple-state
One of the simplest monads that we can craft is a state-passing monad. In Haskell, all state information usually must be passed to functions explicitly as arguments. Using monads, we can effectively hide some state information.
Suppose we have a function f of type a -> b, and we need to add state to this function. In general, if state is of type state, we can encode it by changing the type of f to a -> state -> (state, b). That is, the new version of f takes the original parameter of type a and a new state parameter. And, in addition to returning the value of type b, it also returns an updated state, encoded in a tuple.
For instance, suppose we have a binary tree defined as:
data Tree a
= Leaf a
| Branch (Tree a) (Tree a)Now, we can write a simple map function to apply some function to each value in the leaves:
mapTree :: (a -> b) -> Tree a -> Tree b
mapTree f (Leaf a) = Leaf (f a)
mapTree f (Branch lhs rhs) =
Branch (mapTree f lhs) (mapTree f rhs)This works fine until we need to write a function that numbers the leaves left to right. In a sense, we need to add state, which keeps track of how many leaves we’ve numbered so far, to the mapTree function. We can augment the function to something like:
mapTreeState :: (a -> state -> (state, b)) ->
Tree a -> state -> (state, Tree b)
mapTreeState f (Leaf a) state =
let (state', b) = f a state
in (state', Leaf b)
mapTreeState f (Branch lhs rhs) state =
let (state' , lhs') = mapTreeState f lhs state
(state'', rhs') = mapTreeState f rhs state'
in (state'', Branch lhs' rhs')This is beginning to get a bit unwieldy, and the type signature is getting harder and harder to understand. What we want to do is abstract away the state passing part. That is, the differences between mapTree and mapTreeState are: (1) the augmented f type, (2) we replaced the type -> Tree b with -> state -> (state, Tree b). Notice that both types changed in exactly the same way. We can abstract this away with a type synonym declaration:
type State st a = st -> (st, a)
To go along with this type, we write two functions:
returnState :: a -> State st a
returnState a = \st -> (st, a)
bindState :: State st a -> (a -> State st b) ->
State st b
bindState m k = \st ->
let (st', a) = m st
m' = k a
in m' st'Let’s examine each of these in turn. The first function, returnState, takes a value of type a and creates something of type State st a. If we think of the st as the state, and the value of type a as the value, then this is a function that doesn’t change the state and returns the value a.
The bindState function looks distinctly like the interior let declarations in mapTreeState. It takes two arguments. The first argument is an action that returns something of type a with state st. The second is a function that takes this a and produces something of type b also with the same state. The result of bindState is essentially the result of transforming the a into a b.
The definition of bindState takes an initial state, st. It first applies this to the State st a argument called m. This gives back a new state st' and a value a. It then lets the function k act on a, producing something of type State st b, called m'. We finally run m' with the new state st'.
We write a new function, mapTreeStateM and give it the type:
mapTreeStateM :: (a -> State st b) -> Tree a -> State st (Tree b)
Using these “plumbing” functions (returnState and bindState) we can write this function without ever having to explicitly talk about the state:
mapTreeStateM f (Leaf a) =
f a `bindState` \b ->
returnState (Leaf b)
mapTreeStateM f (Branch lhs rhs) =
mapTreeStateM f lhs `bindState` \lhs' ->
mapTreeStateM f rhs `bindState` \rhs' ->
returnState (Branch lhs' rhs')In the Leaf case, we apply f to a and then bind the result to a function that takes the result and returns a Leaf with the new value.
In the Branch case, we recurse on the left-hand-side, binding the result to a function that recurses on the right-hand-side, binding that to a simple function that returns the newly created Branch.
As you have probably guessed by this point, State st is a monad, returnState is analogous to the overloaded return method, and bindState is analogous to the overloaded >>= method. In fact, we can verify that State st a obeys the monad laws:
Law 1 states: return a >>= f ≡ f a. Let’s calculate on the left hand side, substituting our names:
returnState a `bindState` f
==>
\st -> let (st', a) = (returnState a) st
m' = f a
in m' st'
==>
\st -> let (st', a) = (\st -> (st, a)) st
in (f a) st'
==>
\st -> let (st', a) = (st, a)
in (f a) st'
==>
\st -> (f a) st
==>
f aIn the first step, we simply substitute the definition of bindState. In the second step, we simplify the last two lines and substitute the definition of returnState. In the third step, we apply st to the lambda function. In the fourth step, we rename st' to st and remove the let. In the last step, we eta reduce.
Moving on to Law 2, we need to show that f >>= return ≡ f. This is shown as follows:
f `bindState` returnState
==>
\st -> let (st', a) = f st
in (returnState a) st'
==>
\st -> let (st', a) = f st
in (\st -> (st, a)) st'
==>
\st -> let (st', a) = f st
in (st', a)
==>
\st -> f st
==>
fFinally, we need to show that State obeys the third law: f >>= (\x -> g x >>= h) ≡ (f >>= g) >>= h. This is much more involved to show, so we will only sketch the proof here. Notice that we can write the left-hand-side as:
\st -> let (st', a) = f st
in (\x -> g x `bindState` h) a st'
==>
\st -> let (st', a) = f st
in (g a `bindState` h) st'
==>
\st -> let (st', a) = f st
in (\st' -> let (st'', b) = g a
in h b st'') st'
==>
\st -> let (st' , a) = f st
(st'', b) = g a st'
(st''',c) = h b st''
in (st''',c)The interesting thing to note here is that we have both action applications on the same let level. Since let is associative, this means that we can put whichever bracketing we prefer and the results will not change. Of course, this is an informal, “hand waving” argument and it would take us a few more derivations to actually prove, but this gives the general idea.
Now that we know that State st is actually a monad, we’d like to make it an instance of the Monad class. Unfortunately, the straightforward way of doing this doesn’t work. We can’t write:
instance Monad (State st) where { ... }
This is because you cannot make instances out of non-fully-applied type synonyms. Instead, what we need to do instead is convert the type synonym into a newtype, as:
newtype State st a = State (st -> (st, a))
Unfortunately, this means that we need to do some packing and unpacking of the State constructor in the Monad instance declaration, but it’s not terribly difficult:
instance Monad (State state) where
return a = State (\state -> (state, a))
State run >>= action = State run'
where run' st =
let (st', a) = run st
State run'' = action a
in run'' st'Now, we can write our mapTreeM function as:
mapTreeM :: (a -> State state b) -> Tree a ->
State state (Tree b)
mapTreeM f (Leaf a) = do
b <- f a
return (Leaf b)
mapTreeM f (Branch lhs rhs) = do
lhs' <- mapTreeM f lhs
rhs' <- mapTreeM f rhs
return (Branch lhs' rhs')which is significantly cleaner than before. In fact, if we remove the type signature, we get the more general type:
mapTreeM :: Monad m => (a -> m b) -> Tree a ->
m (Tree b)Now, the nice thing about encapsulating the stateful aspect of the computation like this is that we can provide functions to get and change the current state. These look like:
getState :: State state state
getState = State (\state -> (state, state))
putState :: state -> State state ()
putState new = State (\_ -> (new, ()))Here, getState is a monadic operation that takes the current state, passes it through unchanged, and then returns it as the value. The putState function takes a new state and produces an action that ignores the current state and inserts the new one.
Now, we can write our numberTree function as:
numberTree :: Tree a -> State Int (Tree (a, Int))
numberTree tree = mapTreeM number tree
where number v = do
cur <- getState
putState (cur+1)
return (v,cur)Finally, we need to be able to run the action by providing an initial state:
runStateM :: State state a -> state -> a
runStateM (State f) st = snd (f st)Now, we can provide an example Tree:
testTree =
Branch
(Branch
(Leaf 'a')
(Branch
(Leaf 'b')
(Leaf 'c')))
(Branch
(Leaf 'd')
(Leaf 'e'))and number it:
State> runStateM (numberTree testTree) 1
Branch (Branch (Leaf ('a',1)) (Branch (Leaf ('b',2))
(Leaf ('c',3)))) (Branch (Leaf ('d',4))
(Leaf ('e',5)))This may seem like a large amount of work to do something simple. However, note the new power of mapTreeM. We can also print out the leaves of the tree in a left-to-right fashion as:
State> mapTreeM print testTree
'a'
'b'
'c'
'd'
'e'Nota: sì si potrebbe caricare tutto in GHCi ma sono lazy 😯
This crucially relies on the fact that mapTreeM has the more general type involving arbitrary monads — not just the state monad. Furthermore, we can write an action that will make each leaf value equal to its old value as well as all the values preceding:
fluffLeaves tree = mapTreeM fluff tree
where fluff v = do
cur <- getState
putState (v:cur)
return (v:cur)and can see it in action:
State> runStateM (fluffLeaves testTree) []
Branch (Branch (Leaf "a") (Branch (Leaf "ba")
(Leaf "cba"))) (Branch (Leaf "dcba")
(Leaf "edcba")) In fact, you don’t even need to write your own monad instance and datatype. All this is built in to the Control.Monad.State module. There, our runStateM is called evalState; our getState is called get; and our putState is called put.
This module also contains a state transformer monad, which we will discuss in the section on Transformer [prossimamente].
👽
