In the first and second post of this series I describe a test case (a function evaluator) and a method to tackle its implementation by writing a complex monad in plain Haskell, built as a pile of transformers. All this from the ground up, without importing any library (except basic stuff like Data.Map
and alike) and following the lines described in a presentation by Henrik Nilsson.
All code is available in GitHub, fully covered by tests.
The implementation we’ve come to, handles errors returning Nothing
in all cases of impossible evaluation.
This time we are to provide the capability to weave a mutable state through the computation and modify it to record useful happenings. To start with, state will be an type Int
to be increased by one at each recursive call of the evaluation function.
Teaching a monad to handle mutable state
In order to give any monad m
the capability to pass a state of type s
through each step of its own computation we have to follow the example of the state monad and let m
become part of a function of s
.
The type that expresses this transformation is called StateT
in mtl, whereas Nilsson calls it ST
:
newtype ST s m a = ST (s -> m (a, s))
deriving instance Show (s -> m (a, s)) => Show (ST s m a)
deriving instance Eq (s -> m (a, s)) => Eq (ST s m a)
The monad instance that results by adding state management to m
is the following:
instance (Monad m) => Monad (ST s m) where
return x = ST (\s -> return (x, s))
stsma >>= fastsmb = ST $ \s -> do (aaa, sss) <- unST stsma s
unST (fastsmb aaa) sss
On Github you may find also the corresponding functor and applicative instance definitions, along with the unwrapper and the runner, as Nilsson does not want us to use the pesky Haskell record syntax.
Standing on the shoulders of the giants that came here before us, we accept their warm suggestion to fit the ST
transformer right around the inner I
. That’s to say that ET
(seen in the previous post) will wrap ST
. The type of the resulting evaluation will therefore be (please follow carefully the substitutions):
ET (ST Int I) Value
= ET (ST Int I) (Maybe Value)
= ET (ST (Int -> I (Maybe Value, Int)))
Preparing the monad and running it afterwards
As it is typical with the state monad, each stateful computation is prepared by building the monad and running it afterwards, after providing the initial state. The evaluation function must therefore have type:
Env -> Exp -> ET (ST Int I) Value
and it will have to be run by a function that closes on an Int
(the state monad value at the beginning of the run) and returns a couple (Maybe Value, Int)
. The couple will contain either a Just Value
or a Nothing
(the latter in case of impossibility to evaluate the given expression) and the final state value. We decide to call that function runEval3
:
runEval3 :: Int -> ET (ST Int I) Value -> (Maybe Value, Int)
runEval3 s esm = unI $ unST (unET esm) s
In order to fully appreciate this last step you gotta remember that for Nilsson unST
is actually a runner (corresponding to runStateT
in mtl) and keep in mind the sequence of the onion peeling operations.
A state monad to record each invocation of a given function
In the body of any monadic function we may always use the do-notation abstraction to mimic an imperative step; in the case of a state monad the imitation of giving orders nears perfection. We want to carry a counter through the evaluation of an expression, and we want it to increase each time the evaluation function is invoked, both at the very start and afterwards through recursion. Our guide, Martin Grabmüller calls that state monad tick
.
The way a simpler version of tick
works is explained thoroughly in another post. In this case also I
is involved and the function is:
tick :: ST Int I Int
tick = ST $ \n -> I (n, n+1)
Each time tick
is invoked inside a do-notation or used as body of a function passed to bind
(if you like no sugar in your coffee), the state become the value for an instant, it gets increased and passed further down the computation.
Our expression evaluator begins to get interesting
Following the steps of the Grabmüller paper and using Nilsson’s Lego blocks we come to the following evaluation function:
eval3 :: Env -> Exp -> ET (ST Int I) Value eval3 env (Lit i) = do (lift tick) return $ IntVal i eval3 env (Var name) = do (lift tick) ET $ return $ Map.lookup name env eval3 env (Plus e1 e2) = do (lift tick) v1 <- eval3 env e1 v2 <- eval3 env e2 case (v1, v2) of (IntVal i1, IntVal i2) -> return $ IntVal $ i1 + i2 _ -> eFail eval3 env (Lambda argname body) = do (lift tick) return $ FunVal argname body env eval3 env (App lambda expr) = do (lift tick) FunVal argname body env' <- eval3 env lambda val <- eval3 env expr eval3 (Map.insert argname val env') body
There are two important observation to make:
- the function runs at the
ET
level, thereforetick
must be lifted (details follow), whereaseFail
must not - there is actually no calculation involved so far; as we said before, this is a
Int -> I (Maybe Value, Int)
function at heart
We are kind of winding a spring mouse that will run as soon as it’s fed an Int. This is not only true in the notoriously lazy Haskell: state monads keep quiet even when written in the eager JavaScript.
Here you may admire the function at work in several tests.
Giving ST
all the traits it deserves
The list of typeclasses that our state transformer ST
may want to implement becomes rather long:
MonadTransformer
: gotta implementlift
S
(MonadState
for mtl): this requires implementing agetState/sGet
and asetState/sSet
methods- become itself an error handler, by implementing
eFail
andeHandle
On its turn, ET
may become a state handler. This way we wouldn’t have to lift tick
inside the eval3
function and tick
would work also at the outer ET
layer.
But we started this whole endeavor saying how confusing it is when every transformer is able to do everything. All these implementations are to be found in the Github code, but from now on we will never mention mix-ups of monad effects spanning multiple levels.
Time to write and read, now
The next posts will illustrate the usage of more monad transformers that will change our types into:
- a writer monad that logs the various processing steps
- a reader monad that carries implicitly the evaluation environment and serves it to any computation step that may need to consult it
- a list monad that evaluates n expressions without a single trace of a loop inside the code
3 thoughts on “Understanding monad transformers (3): stateful is beautiful”