content: \documentclass[a4paper,11pt]{article}
  
  \usepackage[margin=2.5cm]{geometry}
  \usepackage{hyperref}
  \usepackage[utf8x]{inputenc}
  
  %include polycode.fmt
  %format alpha = "\alpha"
  
  \title{\bf Monad Transformers Step by Step}
  \author{Martin Grabm{\"u}ller}
  \date{Oct 16 2006\footnote{Ported to newer GHC versions and smaller
  fixes in 2012, 2015, 2018, 2019, 2021, last changes in 2022.}}
  
  \begin{document}
  \maketitle
  
  \begin{abstract}
  \noindent
  In this tutorial, we describe how to use monad transformers in order
  to incrementally add functionality to Haskell programs.  It is not a
  paper about \emph{implementing} transformers, but about \emph{using}
  them to write elegant, clean and powerful programs in Haskell.
  Starting from an evaluation function for simple expressions, we
  convert it to monadic style and incrementally add error handling,
  environment passing, state, logging and input/output by composing
  monad transformers.
  \end{abstract}
  
  \section{Introduction}
  
  This paper gives a step-by-step introduction to monad transformers in
  Haskell.
  
  Monads are a remarkably elegant way for structuring programs in a
  flexible and extensible way.  They are especially interesting in a
  lazy functional language like Haskell, because they allow the
  integration of side-effects into otherwise purely functional programs.
  Furthermore, by structuring a program with monads, it is possible to
  hide much of the necessary book-keeping and plumbing necessary for
  many algorithms in a handful of definitions specific for the monad in
  use, removing the clutter from the main algorithm.
  
  Monad transformers offer an additional benefit to monadic programming:
  by providing a library of different monads and types and functions for
  combining these monads, it is possible to create custom monads simply
  by composing the necessary monad transformers.  For example, if you
  need a monad with state and error handling, just take the |StateT| and
  |ExceptT| monad transformers and combine them.  The goal of this paper
  is to give a gentle introduction to the use of monad transformers by
  starting with a simple function and extending it step by step with
  various monadic operations in order to extend its functionality.  This
  paper is \emph{not} about the theory underlying the monad transformer
  concept, and not about their implementation (except for what is
  necessary for successfully using them).
  
  The reader is expected to be familiar with functional and basic
  monadic programming, such as the use of the |Monad| class and |do|
  notation in Haskell.  Everything else will be explained on the fly.
  
  The Haskell programs in this paper use language features which are not
  in the current Haskell'98 standard, since they use the non-standard
  library modules |Control.Monad.Error| etc.  Both the hierarchical
  module names of these modules and some of their implementation details
  are beyond Haskell'98.  Nevertheless, these extensions are well
  supported in current versions of the Glasgow Haskell compiler (GHC)
  \cite{GHC2006GHCHomepage}.  The programs have been tested using
  GHC version 8.4.4.
  
  The monad transformer modules are inspired by a paper by Mark P. Jones
  \cite{Jones1995FunctionalProgramming}, which gives a very readable
  introduction to monadic programming, but is less practical than this
  paper.
  
  This document has been converted from a literate Haskell script using
  Andres L{\"o}h's \texttt{lhs2TeX}\footnote{\small\tt
  \url{https://www.andres-loeh.de/lhs2tex/}} preprocessor.  The script is
  executable by GHC.  The literate Haskell source file
  \texttt{Transformers.lhs} is available
  Github\footnote{\small\tt
  \url{https://github.com/mgrabmueller/TransformersStepByStep}}.
  
  It is probably best to read this paper near a computer so that you can
  look up the types and descriptions of the various functions used from
  the monad transformer library or the Haskell standard library.  The
  best setup is a printed copy of this paper, a web browser showing the
  online library documentation and a running incarnation of ghci
  with a loaded |Transformers| module (to be introduced below) for
  checking out types interactively using the \texttt{:type} (or
  \texttt{:t}) command.
  
  \subsection{Example Program}
  \label{sec:example-program}
  
  As a running example, an interpreter for a simple programming language
  will be used throughout the paper.  All the code will be located in a module called |Transformers|, which has the following header:
  
  > module Main where
  >
  > import Control.Monad.Identity
  > import Control.Monad.Except
  > import Control.Monad.Reader
  > import Control.Monad.State
  > import Control.Monad.Writer
  >
  > import Data.Maybe
  > import qualified Data.Map as Map
  >
  
  Several of the imported modules beginning with |Control.Monad| are
  only needed when you use the monad transformers defined there.  The
  |Data.Maybe| module defines useful functions for dealing with optional
  values of type |Maybe a|, and the module |Data.Map| defines finite
  maps.  These will be used to define environments (variable-value
  mappings) in our little interpreter.
  
  The following data types for modelling programs in that language will
  be used:
  
  > type Name   =  String                -- variable names
  >
  > data Exp    =  Lit Integer           -- expressions
  >             |  Var Name
  >             |  Plus Exp Exp
  >             |  Abs Name Exp
  >             |  App Exp Exp
  >             deriving (Show)
  >
  > data Value  =  IntVal Integer        -- values
  >             |  FunVal Env Name Exp
  >             deriving (Show)
  >
  > type Env    =  Map.Map Name Value    -- mapping from names to values
  
  The |Name| type is simply a shorthand for the standard |String| type.
  It is used to make clear when we are talking about variable names and
  not about general strings.  The |Exp| data type has variants for
  literal integers (constants), variables, addition, $\lambda$
  expressions (abstractions) and function application.  The programs
  which are to be evaluated will be made up of the |Exp| data type,
  whereas the results are from the |Value| type.  Values are either
  integers or functions (closures).  The |Env| component of a |FunVal|
  is the environment in which the corresponding $\lambda$-abstraction was
  evaluated.
  
  Since the example for using monad transformers will be an interpreter
  for the little language defined above, we start by defining an
  evaluation function.  This function is not monadic and will serve as a
  kind of ``reference implementation''.  The definition of the
  interpreter function, called |eval0|, is straightforward.
  
  > eval0                   ::  Env -> Exp -> Value
  > eval0 env (Lit i)       =   IntVal i
  > eval0 env (Var n)       =   fromJust (Map.lookup n env)
  > eval0 env (Plus e1 e2)  =   let  IntVal i1  = eval0 env e1
  >                                  IntVal i2  = eval0 env e2
  >                             in IntVal (i1 + i2)
  > eval0 env (Abs n e)     =   FunVal env n e
  > eval0 env (App e1 e2)   =   let  val1  = eval0 env e1
  >                                  val2  = eval0 env e2
  >                             in case val1 of
  >                                  FunVal env' n body -> eval0 (Map.insert n val2 env') body
  
  Integer literals simply evaluate to themselves (packaged up in the
  |Value| data type), variables evaluate to the values to which they are
  bound in the environment.  The use of the
  |fromJust|\footnote{|fromJust| has the type |Maybe alpha -> alpha|}
  function is necessary because the |Map.lookup| function returns a
  |Maybe| value.  Note that the use of this function introduces an error
  condition: when a variable is used which is not bound anywhere using a
  $\lambda$ expression, the program will halt with an error
  message. Addition is implemented by simply evaluating both operands
  and returning their sum. Whenever one of the addition operands
  evaluates to a non-number, the pattern matching in the |let|
  expression will fail, also terminating the program with an error
  message.  Abstractions simply evaluate to functional values, which
  capture the environment in which they are evaluated.  Function
  application proceeds similar to addition, by first evaluating the
  function and the argument.  The first expression must evaluate to a
  functional value, whose body is then evaluated in the captured
  environment, extended with the binding of the function parameter to
  the argument value.  The |case| expression used here to deconstruct
  the functional value introduces another error possibility.  In later
  sections of this text, we will handle these error cases using an error
  monad, which gives us more control over their handling.
  
  The definition of |eval0| could be shortened a little bit, for
  example, the |let| expression in the |App| case seems superfluous.
  Nevertheless, the definition given here will make it easier to relate
  it to the monadic versions defined below.
  
  The following example expression, $$12+((\lambda x \to x) (4 + 2))$$
  can be used to test this interpreter and all of the others we will
  define shortly.
  
  > exampleExp = Lit 12 `Plus` (App (Abs "x" (Var "x")) (Lit 4 `Plus` Lit 2))
  
  For example, entering
  
  \begin{verbatim}
      eval0 Map.empty exampleExp
  \end{verbatim}
  in \texttt{ghci} will give the answer
  \begin{verbatim}
      IntVal 18
  \end{verbatim}
  
  \section{Monad Transformers}
  
  The goal of using monad transformers is to have control over aspects
  of computations, such as state, errors, environments etc.  It is a bit
  tedious to reformulate an already written program in monadic style,
  but once that is done, it is relatively easy to add, remove or change
  the monads involved.
  
  In this section, we will first rewrite the example program from
  Section~\ref{sec:example-program} in monadic style and then extend the
  data types and function definitions with various monad transformer
  types and functions step by step.
  
  \subsection{Converting to Monadic Style}
  
  In order to use monad transformers, it is necessary to express
  functions in monadic style.  That means that the programmer needs to
  impose sequencing on all monadic operations using |do| notation, and
  to use the |return| function in order to specify the result of a
  function.
  
  First, we define a monad in which the evaluator will be defined.  The
  following type synonym defines |Eval1 alpha| as a synonym for the type
  |Identity alpha|.  |Identity| is a monad imported from
  |Control.Monad.Identity|, which is perhaps the simplest monad
  imaginable: it defines the standard |return| and |>>=| operations for
  constructing operations in the monad, and additionally a function
  |runIdentity| to execute such operations.  Other than that, the
  identity monad has no effect.  In some sense, we will use this monad
  as a ``base case'', around which other monad transformers can be
  wrapped.  For readability, we also define a function |runEval1|, which
  simply calls |runIdentity|.
  
  > type Eval1 alpha  =   Identity alpha
  >
  > runEval1          ::  Eval1 alpha -> alpha
  > runEval1 ev       =   runIdentity ev
  
  Based on the |Eval1| monad, we now rewrite the |eval0| function as
  |eval1|:
  
  > eval1                   ::  Env -> Exp -> Eval1 Value
  > eval1 env (Lit i)       =   return $ IntVal i
  > eval1 env (Var n)       =   case Map.lookup n env of
  >                               Nothing -> error ("unbound variable: " ++ n)
  >                               Just val -> return val
  > eval1 env (Plus e1 e2)  =   do  ~(IntVal i1)  <- eval1 env e1
  >                                 ~(IntVal i2)  <- eval1 env e2
  >                                 return $ IntVal (i1 + i2)
  > eval1 env (Abs n e)     =   return $ FunVal env n e
  > eval1 env (App e1 e2)   =   do  val1  <- eval1 env e1
  >                                 val2  <- eval1 env e2
  >                                 case val1 of
  >                                   FunVal env' n body ->
  >                                       eval1 (Map.insert n val2 env') body
  
  The first thing to note is that the cases for |Lit|, |Var| and |Abs|
  use the |return| function for specifying their result.\footnote{The
  |($)| operator is function application with low precedence and mainly
  used to avoid parentheses.} In the |Var| case, the evaluation will
  again terminate with an error message if a variable name is not bound.
  
  The |Plus| and |App| cases now evaluate their subexpressions using
  |do|-notation, binding their results to variables.  In the |Plus|
  case, the result is returned using |return|, whereas in th |App| case,
  the function value is further discriminated like in the |eval0|
  function above.
  
  In order to test this interpreter, we have to evaluate the monadic
  action obtained by applying |eval1| to our example expression
  |exampleExp|.  This is done by calling |runEval1| defined earlier:
  
  \begin{verbatim}
      runEval1 (eval1 Map.empty exampleExp)
  \end{verbatim}
  gives
  \begin{verbatim}
      IntVal 18
  \end{verbatim}
  
  To recapitulate: conversion to monadic form consists mainly of
  returning function results using the |return| function, and sequencing
  of monadic actions using |do| notation or the |>>=| or |>>| (monadic
  bind) functions.
  
  \paragraph{Note:}
  The type of |eval1| could be generalized to
  $$
  |eval1 :: Monad m => Env -> Exp -> m Value|,
  $$
  because we do not use any monadic operations other than |return| and
  |>>=| (hidden in the |do| notation).  This allows the use of |eval1|
  in any monadic context, so that instead of
  \begin{verbatim}
      runEval1 (eval1 Map.empty exampleExp)
  \end{verbatim}
  we could write
  \begin{verbatim}
      eval1 Map.empty exampleExp
  \end{verbatim}
  %
  
  at the \texttt{ghci} prompt.  This would run the expression in the
  |IO| monad, because internally the interpreter uses the |print|
  function, which lives in just this monad.  In some contexts, this is a
  nice feature, but in general you will be using some operations
  specific to a particular monad, and this forces your operation to stay
  within that special monad.
  
  \subsection{Adding Error Handling}
  
  We have already seen that our evaluation function is partial, that
  means it will terminate with an error message for some inputs, for
  example for expressions with unbound variables or type errors.
  
  Using monad transformers, we simply go to our local monad transformer
  library and take the |ExceptT| monad transformer, using it to extend
  the basic |Eval1| monad to |Eval2|.
  
  > type Eval2 alpha = ExceptT String Identity alpha
  
  The |String| type argument to |ExceptT| is the type of exceptions, that
  is the values which are used to indicate error conditions.  We use
  |String| here to keep things simple, in a real implementation we might
  want to include source code locations (in a compiler) or time stamps
  (in some kind of web application).
  
  The function for running a computation in the |Eval2| monad changes in
  two ways.  First, the result of evaluation is now of type |Either
  String alpha|, where the result |Left s| indicates that an error has
  occurred with error message |s|, or |Right r|, which stands for
  successful evaluation with result~|r|.  Second, we need to call the
  function |runExceptT| on the given computation to yield an |Identity|
  computation, which can in turn be evaluated using |runIdentity|.
  
  > runEval2     :: Eval2 alpha -> Either String alpha
  > runEval2 ev  = runIdentity (runExceptT ev)
  
  We can now simply change the type of our |eval1| function, giving the
  following version, called |eval2a|.
  
  > eval2a                   ::  Env -> Exp -> Eval2 Value
  > eval2a env (Lit i)       =   return $ IntVal i
  > eval2a env (Var n)       =   case Map.lookup n env of
  >                                Nothing -> error ("Unbound variable: " ++ n)
  >                                Just val -> return val
  > eval2a env (Plus e1 e2)  =   do  ~(IntVal i1)  <- eval2a env e1
  >                                  ~(IntVal i2)  <- eval2a env e2
  >                                  return $ IntVal (i1 + i2)
  > eval2a env (Abs n e)     =   return $ FunVal env n e
  > eval2a env (App e1 e2)   =   do  val1  <- eval2a env e1
  >                                  val2  <- eval2a env e2
  >                                  case val1 of
  >                                     FunVal env' n body ->
  >                                        eval2a (Map.insert n val2 env') body
  
  This version can be run using the |runEval2| function defined above.
  When we apply this function to our example expression, the result only
  varies in that it is wrapped in a |Right| constructor:
  \begin{spec}
  runEval2 (eval2a Map.empty exampleExp) => Right (IntVal 18)
  \end{spec}
  
  But unfortunately, when given an invalid expression, the error
  reporting of the |ExceptT| transformer is not used.  We have to modify
  our definition in order to give useful error messages:
  
  > eval2b                   ::  Env -> Exp -> Eval2 Value
  > eval2b env (Lit i)       =   return $ IntVal i
  > eval2b env (Var n)       =   case Map.lookup n env of
  >                                Nothing -> throwError ("unbound variable: " ++ n)
  >                                Just val -> return val
  > eval2b env (Plus e1 e2)  =   do  e1'  <- eval2b env e1
  >                                  e2'  <- eval2b env e2
  >                                  case (e1', e2') of
  >                                    (IntVal i1, IntVal i2) ->
  >                                        return $ IntVal (i1 + i2)
  >                                    _ -> throwError "type error"
  > eval2b env (Abs n e)     =   return $ FunVal env n e
  > eval2b env (App e1 e2)   =   do  val1  <- eval2b env e1
  >                                  val2  <- eval2b env e2
  >                                  case val1 of
  >                                     FunVal env' n body ->
  >                                        eval2b (Map.insert n val2 env') body
  >                                     _ -> throwError "type error"
  
  Now, when we try to evaluate an invalid expression, we get an error
  message, packaged in the |Left| constructor.  So by matching against
  the result of an evaluation, we can distinguish between normal and
  error results.
  
  \begin{spec}
  runEval2 (eval2b Map.empty (Plus (Lit 1) (Abs "x" (Var "x")))) =>
    Left "type error"
  \end{spec}
  
  A little bit of closer inspection of function |eval2b| reveals that we
  can do even shorter (better?) by exploiting the fact that monadic
  binding in a |do| expression uses the |fail| function whenever a
  pattern match fails. {\footnote{The legacy use of |Monad.fail| in
  do-notation desugaring has been deprecated in favor of
  |MonadFail.fail| as of GHC 8.8.1. See
  \url{https://gitlab.haskell.org/haskell/prime/-/wikis/libraries/proposals/monad-fail} for details.}}
  And, as we have seen, the |fail| function does
  what we want.
  
  > eval2c                   ::  Env -> Exp -> Eval2 Value
  > eval2c env (Lit i)       =   return $ IntVal i
  > eval2c env (Var n)       =   case Map.lookup n env of
  >                                Nothing -> throwError ("unbound variable: " ++ n)
  >                                Just val -> return val
  > eval2c env (Plus e1 e2)  =   do  ~(IntVal i1)  <- eval2c env e1
  >                                  ~(IntVal i2)  <- eval2c env e2
  >                                  return $ IntVal (i1 + i2)
  > eval2c env (Abs n e)     =   return $ FunVal env n e
  > eval2c env (App e1 e2)   =   do  ~(FunVal env' n body)  <- eval2c env e1
  >                                  val2                <- eval2c env e2
  >                                  eval2c (Map.insert n val2 env') body
  
  The drawback of this function is that the error messages only talks
  about ``pattern match failure'', with no specific information about
  why the pattern match fails.  Thus, in order to get good error
  messages, it is better to provide our own calls to |throwError|.  This
  is what we'll do for the final version of the error handling
  evaluation.
  
  > eval2                    ::  Env -> Exp -> Eval2 Value
  > eval2  env (Lit i)       =   return $ IntVal i
  > eval2  env (Var n)       =   case Map.lookup n env of
  >                                Nothing -> throwError ("unbound variable: " ++ n)
  >                                Just val -> return val
  > eval2  env (Plus e1 e2)  =   do  e1'  <- eval2  env e1
  >                                  e2'  <- eval2  env e2
  >                                  case (e1', e2') of
  >                                    (IntVal i1, IntVal i2) ->
  >                                        return $ IntVal (i1 + i2)
  >                                    _ -> throwError "type error in addition"
  > eval2  env (Abs n e)     =   return $ FunVal env n e
  > eval2  env (App e1 e2)   =   do  val1  <- eval2  env e1
  >                                  val2  <- eval2  env e2
  >                                  case val1 of
  >                                     FunVal env' n body ->
  >                                        eval2  (Map.insert n val2 env') body
  >                                     _ -> throwError "type error in application"
  
  \paragraph{Note:} The |Control.Monad.Error| module provides another
  function for catching errors raised using |throwError|, called
  |catchError :: m a -> (e -> m a) -> m a| for arbitrary error monads.
  It can be used for either handling errors locally or passing them on
  to the surrounding calling context.
  
  \subsection{Hiding the Environment}
  
  One way to make the definition of the evaluation function even more
  pleasing is to hide the environment from all function definitions and
  calls.  Since there is only one place where the environment is
  extended (for function application) and two places where it is
  actually used (for variables and $\lambda$ expressions), we can reduce
  the amount of code by hiding it in all other places.  This will be
  done by adding a |ReaderT| monad transformer in order to implement a
  reader monad.  A reader monad passes a value into a computation and
  all its sub-computations.  This value can be read by all enclosed
  computations and get modified for nested computations.  In contrast to
  state monads (which will be introduced in
  Section~\ref{sec:state-monad}), an encapsulated computation cannot
  change the value used by surrounding computations.
  
  We start by simply wrapping a |ReaderT| constructor around our
  previous monad.
  
  > type Eval3 alpha = ReaderT Env (ExceptT String Identity) alpha
  
  The run function |runEval3| must be slightly modified, because we need
  to pass in the initial environment.  The reason is that we will remove
  the environment parameter from the evaluation function.
  
  > runEval3     :: Env -> Eval3 alpha -> Either String alpha
  > runEval3 env ev  = runIdentity (runExceptT (runReaderT ev env))
  
  > eval3               ::  Exp -> Eval3 Value
  > eval3 (Lit i)       =   return $ IntVal i
  > eval3 (Var n)       =   do  env <- ask
  >                             case Map.lookup n env of
  >                                Nothing -> throwError ("unbound variable: " ++ n)
  >                                Just val -> return val
  > eval3 (Plus e1 e2)  =   do  e1'  <- eval3 e1
  >                             e2'  <- eval3 e2
  >                             case (e1', e2') of
  >                               (IntVal i1, IntVal i2) ->
  >                                   return $ IntVal (i1 + i2)
  >                               _ -> throwError "type error in addition"
  > eval3 (Abs n e)     =   do  env <- ask
  >                             return $ FunVal env n e
  > eval3 (App e1 e2)   =   do  val1  <- eval3 e1
  >                             val2  <- eval3 e2
  >                             case val1 of
  >                                FunVal env' n body ->
  >                                   local (const (Map.insert n val2 env'))
  >                                     (eval3 body)
  >                                _ -> throwError "type error in application"
  
  For our running example, we now have to evaluate
  \begin{verbatim}
      runEval3 Map.empty (eval3 exampleExp)
  \end{verbatim}
  
  In all places where the current environment is needed, it is extracted
  from the hidden state of the reader monad using the |ask| function.
  In the case of function application, the |local| function is used for
  modifying the environment for the recursive call.  Local has the type
  |(r -> r) -> m a -> m a|, that is we need to pass in a function which
  maps the current environment to the one to be used in the nested
  computation, which is the second argument.  In our case, the nested
  environment does not depend on the current environment, so we simply
  pass in a constant function using |const|.
  
  \paragraph{Note:} In addition to |ask|, a function |asks| is
  predefined, which expects a function mapping the environment to a
  value.  This can be used to extract individual components of the
  environment by applying |asks| to record selector functions.
  
  \subsection{Adding State}
  \label{sec:state-monad}
  
  Another important application of monads is to provide mutable state to
  otherwise purely functional code.  This can be done using a |State|
  monad, which provides operations for specifying an initial state,
  querying the current state and changing it.
  
  As an example, suppose that we want to add profiling capabilities to
  our little interpreter.  We define the new monad by wrapping a
  |StateT| constructor around the innermost monad, |Identity|.  (In the
  case of |State| and |Error| monads, the order of these constructor
  matters, as we will see below.)  The state maintained in our example
  is a simple integer value, but it could be a value of any data type we
  wish.  Normally, it will be a record holding the complete state
  necessary for the task at hand.
  
  > type Eval4 alpha = ReaderT Env (ExceptT String (StateT Integer Identity)) alpha
  
  The return type of the function |runEval4| changes, because the final
  state is returned together with the evaluation result (error or
  value).  Additionally, we give the initial state as an additional
  parameter so that we gain some flexibility (this can be used, for
  example, to start a computation in the final state of another one).
  
  > runEval4            ::  Env -> Integer -> Eval4 alpha -> (Either String alpha, Integer)
  > runEval4 env st ev  =   runIdentity (runStateT (runExceptT (runReaderT ev env)) st)
  
  For our simple example, we only want to count the number of evaluation
  steps, that is the number of calls to the |eval4| function.  All
  modification happens in a little helper function |tick|, which gets
  the hidden state from the computation, increases the counter and
  stores it back.  The type of |tick| is not |Eval4 ()|, as should be
  expected, because we plan to re-use it in other sections below.
  Therefore, we simply state that the monad in which |tick| will be used
  must be a state monad, and that the state manipulated in that monad is
  numeric, so that we can use the |(+)| operator on it.
  
  > tick :: (Num s, MonadState s m) => m ()
  > tick = do  st <- get
  >            put (st + 1)
  
  By adding a call to the |tick| function in each case, we can count the
  number of applications.
  
  > eval4               ::  Exp -> Eval4 Value
  > eval4 (Lit i)       =   do  tick
  >                             return $ IntVal i
  > eval4 (Var n)       =   do  tick
  >                             env <- ask
  >                             case Map.lookup n env of
  >                                Nothing -> throwError ("unbound variable: " ++ n)
  >                                Just val -> return val
  > eval4 (Plus e1 e2)  =   do  tick
  >                             e1'  <- eval4 e1
  >                             e2'  <- eval4 e2
  >                             case (e1', e2') of
  >                               (IntVal i1, IntVal i2) ->
  >                                   return $ IntVal (i1 + i2)
  >                               _ -> throwError "type error in addition"
  > eval4 (Abs n e)     =   do  tick
  >                             env <- ask
  >                             return $ FunVal env n e
  > eval4 (App e1 e2)   =   do  tick
  >                             val1  <- eval4 e1
  >                             val2  <- eval4 e2
  >                             case val1 of
  >                                FunVal env' n body ->
  >                                   local (const (Map.insert n val2 env'))
  >                                     (eval4 body)
  >                                _ -> throwError "type error in application"
  
  Evaluating our example expression yields:
  \begin{verbatim}
      (Right (IntVal 18),8)
  \end{verbatim}
  meaning that the evaluation was successful, returned the integer 18
  and took 8 reduction steps.
  
  \paragraph{Note:}
  
  When the type of the |Eval4| monad is changed to the following
  (|StateT| and |ExceptT| are swapped), the interpretation of the monad changes.
  
  > type Eval4' alpha    =   ReaderT Env (StateT Integer (ExceptT String Identity)) alpha
  
  Instead of returning a result (error or normal) and a state, either an
  error or a result together with the final state is returned, as can be
  seen in the type of the corresponding run function:
  
  > runEval4'            ::  Env -> Integer -> Eval4' alpha -> (Either String (alpha, Integer))
  > runEval4' env st ev  =   runIdentity (runExceptT (runStateT (runReaderT ev env) st))
  
  The position of the reader monad transformer does not matter, since it
  does not contribute to the final result.
  
  \paragraph{Note:}
  
  The |State| monad also provides an additional function, |gets| which
  applies a projection function to the state before returning it.  There
  is also a function |modify| which can be used to change the internal
  state by applying a function over it.
  
  \subsection{Adding Logging}
  
  The last monad transformer in the toolbox which will be described here
  is |WriterT|.  It is in some sense dual to |ReaderT|, because the
  functions it provides let you add values to the result of the
  computation instead of using some values passed in.
  
  > type Eval5 alpha = ReaderT Env  (ExceptT String
  >                                 (WriterT [String] (StateT Integer Identity))) alpha
  
  Similar to |StateT|, |WriterT| interacts with |ExceptT| because it
  produces output.  So depending on the order of |ExceptT| and |WriterT|,
  the result will include the values written out or not when an error
  occurs.  The values to be written out will be lists of strings.  When
  you read the documentation for the |WriterT| monad transformer, you
  will notice that the type of the output values is restricted to be a
  member of the type class |Monoid|.  This is necessary because the
  methods of this class are used internally to construct the initial
  value and to combine several values written out.
  
  The running function is extended in the same way as earlier.
  
  > runEval5            ::  Env -> Integer -> Eval5 alpha -> ((Either String alpha, [String]), Integer)
  > runEval5 env st ev  =
  >     runIdentity (runStateT (runWriterT (runExceptT (runReaderT ev env))) st)
  
  In the evaluation function, we illustrate the use of the writer monad
  by writing out the name of each variable encountered during evaluation.
  
  > eval5               ::  Exp -> Eval5 Value
  > eval5 (Lit i)       =   do  tick
  >                             return $ IntVal i
  > eval5 (Var n)       =   do  tick
  >                             tell [n]
  >                             env <- ask
  >                             case Map.lookup n env of
  >                                Nothing -> throwError ("unbound variable: " ++ n)
  >                                Just val -> return val
  > eval5 (Plus e1 e2)  =   do  tick
  >                             e1'  <- eval5 e1
  >                             e2'  <- eval5 e2
  >                             case (e1', e2') of
  >                               (IntVal i1, IntVal i2) ->
  >                                   return $ IntVal (i1 + i2)
  >                               _ -> throwError "type error in addition"
  > eval5 (Abs n e)     =   do  tick
  >                             env <- ask
  >                             return $ FunVal env n e
  > eval5 (App e1 e2)   =   do  tick
  >                             val1  <- eval5 e1
  >                             val2  <- eval5 e2
  >                             case val1 of
  >                                FunVal env' n body ->
  >                                   local (const (Map.insert n val2 env'))
  >                                     (eval5 body)
  >                                _ -> throwError "type error in application"
  
  \subsection{What about I/O?}
  
  Until now, we have not considered one importand aspect: input and
  output.  How do we integrate I/O into the monadic definitions we have
  developed so far?  It is not possible to define an I/O monad
  transformer, because the execution of I/O operations in Haskell cannot
  be arbitrarily nested into other functions or monads, they are only
  allowed in the monad |IO|.  Fortunately, the monad transformer library
  provides us with the infrastructure to easily integrate I/O operations
  into our framework: we simply substitute |IO| where we have used
  |Identity|!  This is possible because |Identity| is the base monad,
  and as we have seen, the function |runIdentity| for evaluating actions
  in this monad is always applied last.
  
  > type Eval6 alpha = ReaderT Env  (ExceptT String
  >                                 (WriterT [String] (StateT Integer IO))) alpha
  
  The return type of |runEval6| is wrapped in an |IO| constructor, which
  means that the running an |Eval6| computation does not directly yield
  a result, but an I/O computation which must be run in order to get at
  the result.  Accordingly, the |runIdentity| invocation disappears.
  
  > runEval6           ::  Env -> Integer -> Eval6 alpha -> IO ((Either String alpha, [String]), Integer)
  > runEval6 env st ev  =
  >     runStateT (runWriterT (runExceptT (runReaderT ev env))) st
  
  In the |eval6| function we can now use I/O operations, with one minor
  notational inconvenience: we have to invoke the operations using the
  function |liftIO|, which lifts the I/O computation into the currently
  running monad.  As an example, we chose to print out each integer
  constant as soon as it is evaluated.  (We don't think this is good
  style, but it illustrates the point and sometimes makes a good
  debugging technique.)
  
  > eval6               ::  Exp -> Eval6 Value
  > eval6 (Lit i)       =   do  tick
  >                             liftIO $ print i
  >                             return $ IntVal i
  > eval6 (Var n)       =   do  tick
  >                             tell [n]
  >                             env <- ask
  >                             case Map.lookup n env of
  >                                Nothing -> throwError ("unbound variable: " ++ n)
  >                                Just val -> return val
  > eval6 (Plus e1 e2)  =   do  tick
  >                             e1'  <- eval6 e1
  >                             e2'  <- eval6 e2
  >                             case (e1', e2') of
  >                               (IntVal i1, IntVal i2) ->
  >                                   return $ IntVal (i1 + i2)
  >                               _ -> throwError "type error in addition"
  > eval6 (Abs n e)     =   do  tick
  >                             env <- ask
  >                             return $ FunVal env n e
  > eval6 (App e1 e2)   =   do  tick
  >                             val1  <- eval6 e1
  >                             val2  <- eval6 e2
  >                             case val1 of
  >                                FunVal env' n body ->
  >                                   local (const (Map.insert n val2 env'))
  >                                     (eval6 body)
  >                                _ -> throwError "type error in application"
  
  \section{Conclusion}
  
  Monad transformers are a powerful tool in the toolbox of a functional
  programmer.  This paper introduces several of the monad transformers
  available in current Haskell implementations, and shows how to use and
  combine them in the context of a simple functional interpreter.
  
  We have not covered all monad transformers presently implemented in
  Haskell (e.g., continuation and list monad transformers) and recommend
  to read the library documentation available from the Haskell web site for
  additional information.
  
  The use of monad transformers makes it very easy to define specialized
  monads for many applications, reducing the temptation to put
  everything possibly needed into the one and only monad hand-made for
  the current application.
  
  \bigskip
  Happy hacking in Haskell!
  
  \section*{Acknowledgements}
  
  Thanks to Christian Maeder, Bruno Mart{\'i}nez and Tomasz Zielonka for
  their valuable feedback and suggestions for improvement. Also thanks
  to G{\'a}bor Lipt{\'a}k, Franklin Chen, Alexey Pastuhov, Fabian
  Schneider and Julia Jiang for providing patches to fix issues and to
  port this tutorial to newer GHC versions.
  
  \bibliographystyle{plain}
  \bibliography{bibliography}
  
  \end{document}
  
  > eval4'               ::  Exp -> Eval4' Value
  > eval4' (Lit i)       =   return $ IntVal i
  > eval4' (Var n)       =   do env <- ask
  >                             case Map.lookup n env of
  >                                Nothing -> throwError ("unbound variable: " ++ n)
  >                                Just val -> return val
  > eval4' (Plus e1 e2)  =   do  e1'  <- eval4' e1
  >                              e2'  <- eval4' e2
  >                              case (e1', e2') of
  >                               (IntVal i1, IntVal i2) ->
  >                                   return $ IntVal (i1 + i2)
  >                               _ -> throwError "type error in addition"
  > eval4' (Abs n e)     =   do  env <- ask
  >                              return $ FunVal env n e
  > eval4' (App e1 e2)   =   do  val1  <- eval4' e1
  >                              val2  <- eval4' e2
  >                              case val1 of
  >                                FunVal env' n body ->
  >                                   local (const (Map.insert n val2 env'))
  >                                     (eval4' body)
  >                                _ -> throwError "type error in application"
  
  > main = do let r0 = eval0 Map.empty exampleExp
  >           print r0
  >           let r1 = runEval1 (eval1 Map.empty exampleExp)
  >           print r1
  >           let r2a = runEval2 (eval2a Map.empty exampleExp)
  >           print r2a
  >           let r2b = runEval2 (eval2b Map.empty exampleExp)
  >           print r2b
  >           let r2c = runEval2 (eval2c Map.empty exampleExp)
  >           print r2c
  >           let r2 = runEval2 (eval2 Map.empty exampleExp)
  >           print r2
  >           let r3 = runEval3 Map.empty (eval3 exampleExp)
  >           print r3
  >           let r4 = runEval4 Map.empty 0 (eval4 exampleExp)
  >           print r4
  >           let r4' = runEval4' Map.empty 0 (eval4' exampleExp)
  >           print r4'
  >           let r5 = runEval5 Map.empty 0 (eval5 exampleExp)
  >           print r5
  >           let r5' = runEval5 Map.empty 0 (eval5 (Var "x"))
  >           print r5'
  >           r6 <- runEval6 Map.empty 0 (eval6 exampleExp)
  >           print r6
  >           r6' <- runEval6 Map.empty 0 (eval6 (Var "x"))
  >           print r6'
  
  
  --  LocalWords:  ExceptT StateT GHC Exp deconstruct monad's ReaderT Env
  