In the starting 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 first implementation, not even monadic, crashes at the tiniest problem. Therefore, the first onion layer is gonna be an error-handling monad transformer but, before starting, we need to have a round core to cover.
Every onion starts from a round soft core
Before covering the onion with the various transformer layers, we must put a monad at the heart of the construction.
Because of the quirky nature of Haskell mtl uses IO
, we’ll use Identity
instead, as we like to keep things simple.
The first step must be therefore to define I
, the Identity monad, plus the unwrapper and the runner (which in this case are the same thing):
newtype I a = I a
deriving (Show, Read, Eq)
-- unwrap the monad
unI :: I a -> a
unI (I a) = a
-- run the monad
runI :: I a -> a
runI = unI
instance Monad I where
return = I
ia >>= faib = faib (unI ia)
The running code contains also the definition of the Functor and Applicative instances, so to keep GHC happy without having to invoke any mysterious compiler spell.
The monadic evaluation function eval1
will just box/unbox stuff while walking through the same algo seen previously, and will crash just as often as before:
eval1 :: Env -> Exp -> I Value
eval1 env (Lit i) = return $ IntVal i
eval1 env (Var name) = return $ fromJust $ Map.lookup name env
eval1 env (Plus e1 e2) = do (IntVal i1) <- eval1 env e1
(IntVal i2) <- eval1 env e2
return $ IntVal $ i1 + i2
eval1 env (Lambda argname body) = return $ FunVal argname body env
eval1 env (App lambda expr) = let (FunVal argname body env') = unI $ eval1 env lambda
val = unI $ eval1 env expr
in eval1 (Map.insert argname val env') body
After that, we’ll use the unbox function one final time to extract the Value
:
runEval1 :: I Value -> Value
runEval1 = unI
All this is to be seen in action by running TestNilsson_01.hs in GHC.
The first onion layer handles errors coming out from the Identity core
Next we place an error-handling monad transformer around I
. Usually it is ErrorT
, based on Either String
, but Nilsson chooses an ET
(shorter name to avoid any possible clash with mtl) which is actually the transformer MaybeT
. In case of error we’ll avoid crashes, but there will be no specific error message.
newtype ET m a = ET (m (Maybe a))
deriving instance Show (m (Maybe a)) => Show (ET m a)
deriving instance Eq (m (Maybe a)) => Eq (ET m a)
In our testcase, we’ll have an ET I Value = ET (I (Maybe Value))
. The boxed result will either be a Just Value
or a Nothing
.
The definition of the error monad instance produced by the ET
transformer is the following:
instance (Monad m) => Monad (ET m) where
return a = ET (return (Just a))
etma >>= faetmb = ET $ do maybea <- unET etma
case maybea of
Just a -> unET (faetmb a)
Nothing -> return Nothing
As usual, the running code contains the functor and applicative instances as well, along with the unwrapper and the runner.
The eval2
evaluating function with error handling is ready:
eval2 :: Env -> Exp -> ET I Value -- ET I (Maybe Value)
eval2 env (Lit i) = return $ IntVal i
eval2 env (Var name) = case (Map.lookup name env) of
Just v -> return v
Nothing -> eFail
eval2 env (Plus e1 e2) = do v1 <- eval2 env e1
v2 <- eval2 env e2
case (v1, v2) of
(IntVal i1, IntVal i2) -> return $ IntVal $ i1 + i2
_ -> eFail
eval2 env (Lambda argname body) = return $ FunVal argname body env
eval2 env (App lambda expr) = do v1 <- eval2 env lambda
v2 <- eval2 env expr
case v1 of
FunVal argname body env' -> eval2 (Map.insert argname v2 env') body
_ -> eFail
The traits of a generic error handler…
The definition of eFail
is not part of ET m
(for a monad you only need return
and bind
); it is part of that typeclass which in Haskell is called a MonadError
. Nilsson calls it E
. What MonadError
s do for a living is:
- fail gently
- provide a
catch
instruction in case atry
instruction fails
We all want ET m
to be member of typeclass E
, of course…
-- kind of MonadError
class (Monad m) => E m where
eFail :: m a -- save the day returning a monad anyhow
eHandle :: m a -> m a -> m a --tryclause->catchclause->pick_one
instance (Monad m) => E (ET m) where
eFail = ET (return Nothing)
eHandle tryetma catchetma = ET $ do maybetry <- unET tryetma
case maybetry of
Just _ -> return maybetry
Nothing -> unET catchetma
For the first time we have tests that can handle failures as well.
…and those of a monad transformer
There’s nothing done so far that makes ET
pluggable as member of a pile of monad transformers. Using once more the onion analogy (which is kinda becoming boring) there will be more layers coming. Computations at those levels will certainly not implement error handling and will want instead to call ET
each time something goes awry. ET
has to play ball.
What makes any monad transformer capable of working alongside other transformers is the shared belonging to the MonadTrans
typeclass, which Nilsson calls MonadTransformer
. This means implementing a lift
method. lift
takes whatever monad from the underlying layer and makes it runnable up here. In the case of ET
it’s just a matter of unboxing/boxing:
instance (Monad m) => MonadTransformer ET m where
lift :: m a -> ET m a -- ET m a = ET m (Maybe a)
lift ma = ET $ do a <- ma
return (Just a)
and, if you prefer it with no sugar…
lift ma = ET $ ma >>= \a -> return (Just a)
The monadic expression evaluator won’t crash anymore and its error-recovering magic will be callable from every layer of the onion by implementing lift
at each level.
In the next installment of this series we will add the capability to handle state; this will allow to record many interesting things happening during the evaluation of a complex expression.
4 thoughts on “Understanding monad transformers (2): first thing get yourself covered”