Understanding monad transformers (2): first thing get yourself covered

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 MonadErrors do for a living is:

• fail gently
• provide a catch instruction in case a try 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.

Advertisements