The baby error monad (with exercises)

The error monad offers a clean, compositional way to detect and report errors without taking down an entire computation. And when the error monad appears in the return type of a function, its presence alerts the programmer to the possibility that the function might fail.¹ The error monad is a key component in our parsers, and it will also be a key part of other program transformations we write in the future, starting with projection functions in module 5.

You’ll learn the error monad by starting with the “baby” error monad. It is a simplified version that has short constructor names and no messages. A value in the error monad has one of two forms:

• It is a “real” value wrapped in S (for success)
• It is the error indication E.

Value constructors S and E and type error are defined as follows:

datatype 'a error = S of 'a | E

A value of type 'a error represents a computation of ’a that might fail.

::: new

If you like videos, Stephen Edwards has made a good video about the error monad.² The code is in Haskell, and in the video,

• error is called Maybe.
• S is called Just.
• E is called Nothing.

The video is optional; you can complete everything without viewing it.

:::a

In this handout, you’ll learn about the error monad by completing a bunch of algebraic laws. It may not look like you’ve been given enough information, but in each case, there is only one sensible answer that typechecks. Bring your completed laws to lab.

Success

A computation is usually composed of sub-computations, and some of those sub-computations might be guaranteed to succeed. To express a computation that might fail but is guaranteed to succeed, we have the succeed function:

val succeed : 'a -> 'a error

succeed a = S a

Application in the error monad

Sub-computations are often independent. For example, if we are translating function definitions in a Scheme program, each definition can be translated independently. To compose independent computations, Conor McBride and Ross Paterson popularized a model of applicative programming with effects. (Here, the effect is potential failure.) The central part of the model is a function application: one sub-computation produces a function, and the other produces the function’s argument. Application is performed by the <*> function, which is written using infix notation:

val <*>  : ('a -> 'b) error * 'a error -> 'b error

1. Study the types, then complete these algebraic laws:

   S f <*> S a = ...
   E   <*> S a = ...
   S f <*> E   = ...
   E   <*> E   = ...

   Make sure each law typechecks.

Any computation written using only succeed and <*> can always be rewritten as a function of the form

succeed f <*> c_1 <*> ... <*> c_n

Any abstraction that supports these operations, together with suitable laws, is called an applicative functor. The error monad is an applicative functor.

Application of a pure function

The example above, where succeed f is applied by <*>, is quite common. This idiom is supported by a special-case abbreviation:

val <$> : ('a -> 'b) * 'a error -> 'b error

f <$> c = succeed f <*> c

2. The idiom is easier to understand without the abbreviation. Complete these algebraic laws:

   f <$> S a =  ...
   f <$> E   =  ...

Sometimes the <$> function is more useful in its Curried form:³

val map : ('a -> 'b) -> ('a error -> 'b error)

3. Complete these laws:

   map f (S a) = ...
   map f E     = ...

Nested and dependent computations

Sometimes a computation that might fail can produce, on success, a result from another computation that might fail. They aren’t independent any more! Here’s a way to collapse nested failure into a single failure

val join : 'a error error -> 'a error

4. Complete these algebraic laws:

   join E         = ...
   join (S E)     = ...
   join (S (S a)) = ...

An abstraction that supports succeed, map, and join is called a monad. A monad is also an applicative functor, and the <$> and <*> operations are related to map and join by these laws:

f  <$> ca = join (map (fn a => succeed (f a)) ca)

cf <*> ca = join ((fn f => f <$> ca) <$> cf)

An easier way to sequence dependent computations is by the monadic bind operator. It takes a computation c and a continuation k. The continuation enables the later computation and its effects to depend on the value of the earlier computation. It’s a capability that an applicative functor is not required to provide, and we’ll use it rarely. But it is the basis of Haskell’s do notation.

5. Complete the algebraic laws for monadic bind:

   val >>= : 'a error * ('a -> 'b error) -> 'b error
   
   E   >>= k  =  ...
   S a >>= k  =  ...

Function composition with failure

Big chunks of the Universal Forward Translator are written as function compositions, but some of those functions can fail. Such functions can be elegantly composed using “Kleisli composition,” sometimes called the “fish operator”:

val >=> : ('a -> 'b error) * ('b -> 'c error) -> ('a -> 'c error)

6. Complete this algebraic law with two cases, one for each form of f a:

   (f >=> g) a = ..., when f a = ...

We’ll use this composition together with a composition for pure functions that is inspired by the Elm programming language:

val >>> : ('a -> 'b) * ('b -> 'c) -> ('a -> 'c)

(f >>> g) x = g (f x)

Errors in lists

Another common idiom in the compiler is to apply a potentially failing function to each element of a list. The result has type ’a error list, but we really want 'a list error:

(* list functions *)
val list : 'a error list -> 'a list error
val mapList : ('a -> 'b error) -> ('a list -> 'b list error)

list []          = S []
list (E :: _)    = E
list (S a :: xs) = S (a :: as), when list xs == S as
                 = E            when list xs == E

mapList f = List.map f >>> list