Notes on monads

Introduction

Over the lectures from 10/2–10/9, we developed the idea of a monad as an abstraction and generalization of our techniques for extending the λ-calculus with computational effects, such as exceptions and state. These notes review that development.

Generalizing effects

Our implementations of computational effects shared two common operations. The first was a way to inject values into the effect. For example, in our implementation of exceptions (see Lcex.hs), we use the Ok constructor to denote non-exception values.

eval _ (EInt x) =
  Ok (VInt x)

Similarly, in our implementation of state (see Lcst0.hs), we express values as having the constant state transformer:

eval _ (EInt x) =
  \s -> (VInt x, s)

The second is a way to combine computations. For example, the code for evaluating an EAdd expression needs to do two sub-computations, one for each branch. Without computational effects, this is straightforward.

eval h (EAdd e1 e2) =
  let VInt x1 = eval h e1
      VInt x2 = eval h e2 in
  VInt (x1 + x2)

However, with computational effects around, it is not as simple. For example, with exceptions, either the evaluation of e1 or the evaluation of e2 may raise an exception. In either case, the result of evaluating EAdd e1 e2 should raise an exception as well. One example of this pattern:

eval h (EAdd e1 e2) =
  case eval h e1 of
    Exception -> Exception
    Ok (VInt x1) ->
      case eval h e2 of
        Exception -> Exception
        Ok (VInt x2) -> Ok (VInt (x1 + x2))

This style of programming would rapidly become tedious. We discovered that, by introducing some simple combinators, we could simplify the task of programming with effects. These combinators are: the return function (which we initially called ok), which injects values (or pure computations) into effectful computations; and, the >= function (which we originally called andThen), which combines computations. Using these combinators, the previous evaluation case would be written as:

eval h (EAdd e1 e2) =
  eval h e1 >>= \ (VInt x1) ->
  eval h e2 >>= \ (VInt x2) ->
  return (VInt (x1 + x2))

We also observed that these operations characterize a number of models of computational effects, not just exceptions. The generalization of these models is called a monad, and is captured by the following type class declaration.

class Monad m where
  return :: t -> m t
  (>>=) :: m t -> (t -> m u) -> m u

In this definition, m is a type constructor, not a type. That is: there are not values of type m directly, but rather values of type m t for arbitrary types t. We have already seen several examples of type constructors, such as Maybe (there are no Maybe values, but there are Maybe Int, Maybe Bool, Maybe (Maybe Bool) values, and so forth), and the list type constructor [].

Syntax for monads

The monadic combinators make it much simpler to write code that deals with computational effects, but still require a certain amount of syntactic overhead. Monads are common enough in Haskell that they language provides special notation for writing expressions of monadic type---the so-called do notation

In general, do notation consists of the keyword do, followed by any number of statements. A state can be either an expression e (of monadic type), or a binding x <- e, where x is any variable (or pattern), and e is an expression (also of monadic type). The last statement in a do block cannot be a binding.

We have already seen several examples of do notation, in the type checker. For example, the type checking code for addition is

check g (EAdd e1 e2) =
  do TInt <- check g e1
     TInt <- check g e2
     return TInt

The first two statements are bindings, requiring that the recursive calls check g en each returns TInt. The final statement is an expression. Note that both the calls to check and return produce monadic computations themselves.

The translation from do notation to the monadic combinators is straightforward. Each binding is translated into an application of the >>= operator. For example, the simple block

do x <- e1
   e2

would be translated to the following application of the >>= operator.

e1 >>= \ x -> e2

Longer do blocks can be translated by recursively applying the same simple translation step. For example, the block

do x <- e1
   y <- e2
   e3

could be translated by translating the first binding

e1 >>= \ x ->
do y <- e2
   e3

and then by applying the same translation again, this time to the second binding

e1 >>= \ x ->
e2 >>= \ y ->
e3

Intermediate statements need not be bindings; in these cases, the intermediate computations are run simply for their effects, not for their results. An example of this appears in the driver code from the various homework assignments:

go s =
    do e <- parse s
       e' <- desugar e
       check' e'
       v <- eval' e'
       return (show v)

We need to run the type checker to make sure that expressions are well-typed; however, we do not need the result of type checking. Expressions like these can simply be treated as bindings that ignore their results. We could express this using a wild card pattern, such as the following:

go s =
    do e <- parse s
       e' <- desugar e
       _ <- check' e'
       v <- eval' e'
       return (show v)

Now the desugaring proceeds as normal; for example, the subexpression beginning with the call to check is desugared to

check' e' >>= \ _ ->
eval' e' >>= \ v ->
return (show v)

This pattern is common enough that the Haskell prelude defines an operator to sequence monadic expressions without capturing their results, called >> and of type m t -> m u -> m u. We could have chosen to use this combinator instead, which would give the following desugaring:

check' e' >>
eval' e' >>= \ v ->
return (show v)

This is purely a matter of style; there is no computational or typing difference between e1 >>= \ _ -> e2 and e1 >> e2

A note about functors

The definition above leaves out one important part of the prelude definition of the Monad class. Haskell monads also have to be instances of the Functor and Applicative classes. Luckily, for the vast majority of monads (including all the ones in this course), the Functor and Applicative instances carry no information that is not already in the Monad instance. So, we can use a common template to provide these instances. If we have an instance Monad T, where T is any Haskell type expression, then we can add

instance Functor T where
  fmap f = (>>= return . f)
instance Applicative T where
  pure = return
  f <*> a = f >>= \f' -> a >>= \a' -> f' a'

to supply the necessary superclass definitions.