Blog

In addition to it being useful, it is also cursed and the curse of the monad is that once you get the epiphany, once you understand - “oh that’s what it is” - you lose the ability to explain it to anybody.

– Douglas Crockford

If you are familiar with `Maybe`

and how it behaves as a monad, you can
safely skip this chapter. If you have doubts about using the `do`

notation or with `bind`

and `return`

, read on. Maybe the curse is broken?

The `Maybe`

type class is the core sequencing construct that will form the heart of our evaluators and eventual type inference routines. The Haskell `Maybe`

type class definition provides two constructors, `Just x`

and `Nothing`

. By convention `Just x`

contains a value resulting from a successful computation while `Nothing`

indicates an error or exception. Literally, the computation result is `Nothing`

. Treating `Maybe`

as monad and using the `do`

notation to structure computations provides an ideal basis for writing language interpreters.

To understand how the `Maybe`

monad will be used, let’s take a quick look at a definition of `Maybe`

as an instance of `Monad`

:

```
instance Monad (Maybe e) where
return = Just
Just m >>= k = (k m)
Nothing >>= _ = Nothing
```

All `Monad`

instances must define `return`

and `>>=`

, the infix representation for `bind`

. To define `Maybe`

as a monad, this definition provides definitions for both. `return`

is defined as simply the `Just`

constructor making `return x`

the same as `Just x`

:

```
return = Just
```

As an example, `return 1`

results in `Just 1`

. `Just x`

indicates a good result. Thus, `return x`

will be used at the end of `do`

expressions when a good value result should be returned by an interpreter. One may use `return`

and `Just`

interchangeably, but it is best to use `return`

when building a monadic construct.

Two cases define the behavior of `>>=`

for `Maybe`

’s two constructors. `>>=`

is an infix operation and its definition may look a bit odd, but we’re simply defining one case each for `Just`

and `Nothing`

:

```
Just m >>= k = (k m)
Nothing >>= _ = Nothing
```

The first line says that given `(Just m)`

and a function `k`

over the type of `m`

, call `k`

on `m`

. Pretty simple, but lets say it again. `(Just m) >>= k`

returns `(k m)`

. `(Just m)`

bind `k`

results in `(k m)`

. That’s really all there is two it. Bind takes an instance of `Just`

, pulls out the argument, and applies `k`

to it.

But there’s a bit more to it. The type of `bind`

taken from the Haskell definitionsays something important about the type of `k`

:

```
(>>=) :: Monad m => m a -> (a -> m b) -> m b
```

Yikes. Just read carefully and you’ll be just fine, but let’s dump the type parameter notation and just talk about `Maybe`

:

```
(>>=) :: Maybe a -> (a -> Maybe b) -> Maybe b
```

Maybe this is a bit clearer. Importantly, `a`

and `b`

are type variables, not term variables. meaning their values are types. In this case, the definition says the function argument to `>>=`

must take a type `a`

and produce a `Maybe b`

. The result type need not be the same as the input type, but it must be either `Just x`

or `Nothing`

. So, `>>=`

does what we said earlier plus a little bit more. It pulls the argument to `Just`

out and applies a function *whose range must be a Maybe*. Why? We’ll talk through this in a minute, but think carefully about what this might do:

```
(Just 3) >>= j >>= k >>= l >>= m
```

Maybe execute `j`

, `k`

, `l`

and `m`

in sequence? Pretty cool actually, but you may not see it just yet. Let’s move on.

The second case for the `>>=`

definition says that given `Nothing`

as the first argument to `>>=`

return `Nothing`

regardless of the second argument. Again pretty simple, but lets say it again. `Nothing >>= k`

will simply return `Nothing`

*regardless of what k is*.

`Nothing`

simply passes through the bind operation as if its second argument were an identity function. For example:```
Nothing >>= j >>= k >>= l >>= m
== Nothing
```

results in `Nothing`

regardless of what `j`

, `k`

, `l`

and `m`

are. They are effectively skipped.

Thinking about `>>=`

by putting the two definition cases together it would seem that `Just x >>= k`

applies `k`

to the value `x`

and `Nothing >>= k`

always results in `Nothing`

. Remember the choice of `Just`

for values and `Nothing`

for errors we made earlier? This is exactly the behavior we want if we’re executing operations in sequence where failure of one operation propagates through the remaining execution sequence. This is exactly the monad behavior our language interpreters, elaborators and type checkers are all structured around.

This sequencing and handling of `Nothing`

is not a part of `j`

, `k`

, and `l`

, but a part of the bind operator. As long as each function takes a value as input and produces a `Maybe`

value as output, `>>=`

takes care of managing the sequencing behavior. In essence, this is what a monad always does. A monad always takes care of something in the background that is inherent to the computation being performed. A monad implements a model of computation. Importantly, *you don’t write the code for the computation model*, it will always be built into the monad.

Now we’re getting weird. Let’s get a bit more concrete and look at using the `Maybe`

monad and some notations that make it more comfortable.

Write an expression that does the following:

- Subtract 10 from an initial value and throw an error if negative
- Square the result from 1. and throw an error if odd
- Subtract 5 from the result of 2.

Now let’s write a set of functions that perform these operations, including generating errors. We’ll use `Just`

to return values and `Nothing`

to return errors in the canonical `Maybe`

style:

```
a = \x -> if x<10 then Nothing else (Just (x-10))
b = \y -> if (y `mod` 2)==0 then (Just (y*y)) else Nothing
c = \z -> (Just (z-5))
```

Hopefully it’s clear these expressions perform the three operations and check for local errors. Names for the expressions aren’t necessary, but will make things a bit simpler. Without using `Maybe`

as a monad, we can compose these operations to do what we want on the value 10:

```
case (a x)
Nothing -> Nothing
(Just y) -> case (b y)
Nothing -> Nothing
(Just z) -> (c z)
```

Not horrible, but when composing operations this implementation must worry about pushing around `Nothing`

to handle error cases. The nested `case`

expressions implement managing `Nothing`

in this fashion, which is most likely what you are used to doing. Now let’s use the `Maybe`

as a monad and take advantage of bind:

```
(return x) >>= a >>= b >>= c
```

Remember what `>>=`

does. It takes a `Maybe`

value does one of two things. If the input is `Just x`

it performs an operation on `x`

and returns the result or an error. If the input is `Nothing`

it just returns nothing. Pretty cool, but how does it work?

Lets think this through for two examples. In the first, let’s use `x=10`

and walk through the code. 10 is initially lifted into the Maybe monad using `return`

. Remember the first argument to `>>=`

must be a Monad making the `return`

necessary. `(return 10)`

is equal to `(Just 10)`

, so `a`

will perform it’s operation that will generate `Just`

or `Nothing`

. In this case, `10<10`

is false and `(a 10)`

returns `(Just (10-10))`

or `(Just 0)`

. So:

```
(return 10) >>= a
== (Just 0)
```

Next `((return 10) >>= a)`

is bound to `b`

:

```
((return 10) >>= a) >>= b
== (Just 0) >>= b
```

The value of `((return 10) >>= a`

is `(Just 0)`

so `b`

is called on 0. `(b 0) = (Just 0)`

because `0`

is even. The result is now bound to `c`

:

```
(((return 10) >>= a) >>= b) >>= c
== (Just 0) >>= c
```

`c 0 = (Just -5)`

because `c`

always subtracts 5 from its input and never generates an error. Thus our final result is:

```
(Just -5)
```

What we get is exactly what we want `Just (c (b (a 10)))==(Just -5)`

. To which you should say big deal. If no errors occur it is easy to write any fragment, including this one. Let’s try a case that does throw an error:

```
(return 11) >>= a >>= b >>= c
```

Looking first at `(return 11) >>= a`

it works as it did before. `11<10`

is false so we get `(Just 1)`

and the result is once again bound to `b`

:

```
(Just 1) >>= b
```

`b`

responds to `(Just 1)`

differently because `1`

is odd and `1 mod 2`

is not `0`

. This time `b`

returns `Nothing`

and we must now evaluate:

```
Nothing >>= c
```

The case for `>>=`

with an input of `Nothing`

immediately returns `Nothing`

without invoking `c`

. `c`

needn’t worry about implementing a pass-through for errors that come before it in sequence because it is never called if `Nothing`

is input to `>>=`

as the first argument.

One more, this time with emphasis on `Nothing`

pass-through:

```
(Just 9) >>= a >>= b >>= c
== Nothing
```

In this case `(a 9)`

results in `Nothing`

because `9<10`

. Now the magic happens:

```
(return 9) >>= a >>= b >>= c
== Nothing >>= b >>= c
== Nothing >>= c
== Nothing
```

Each time `Nothing`

is bound to a function, `Nothing`

results because of the definition of `>>=`

. Not because of the definition of any particular participating function, but because of the `Maybe`

monad itself. Any function that consumes a value and produces a `Maybe`

result can be dropped and the same behavior results.

The only usage issue is transforming the initial value into a `Maybe`

type using `return`

before the first call to bind. `Just`

would have worked equally well, but `return`

is general to any monad. We call this *lifting* `10`

into the `Maybe`

type. Small price to pay for not managing all of the error handling. We can even get rid of that by embedding the expression in a function:

```
f x = (return x) >>= a >>= b >>= c
```

Pretty cool, but there’s even more. The ever present `do`

notation.

The previous implementation uses names for the various operations composed using `bind`

in the examples above. To start to understand `do`

, let’s pull the names off and use the expressions directly in our composition:

```
(Just 10)
>>= \x -> if x<10 then Nothing else (Just (x-10))
>>= \y -> if (y `mod` 2)==0 then (Just (y*y)) else Nothing
>>= \z -> (Just (z-5))
```

With a bit of formatting magic we get:

```
(Just 10) >>= \x ->
if x<10 then Nothing else (Just (x-10)) >>= \y ->
if (y `mod` 2)==0 then (Just (y*y)) else Nothing >>= \z ->
(Just (z-5))
```

Literally nothing changes other than replacing names with functions and how the expression is indented.

The reason for the reformatting is to associate the input parameter for each function with the expression it is bound to by the function call. `x`

is bound to `Just 10`

, `y`

is bound to evaluating the first `if`

expression and `z`

is bound to evaluating the second `if`

expression. Now lets translate each instance of `>>=`

into an instance of `<-`

using the following transformation:

```
m >>= \n == n <- m
```

Performing this transformation gives us this `do`

expression:

```
x <- (Just 10)
y <- if x<10 then Nothing else (Just (x-10))
z <- if (y `mod` 2)==0 then (Just (y*y)) else Nothing
(Just (z-5))
```

Do you recognize this? Maybe with a few more decorations and formatting:

```
do x <- (Just 10)
y <- if x<10 then Nothing else (Just (x-10))
z <- if (y `mod` 2)==0 then (Just (y*y)) else Nothing
(return (z-5))
```

Bingo! We have the `do`

notation working backwards from the `>>=`

notation. Of course we usually go the other way, but this explains the “magic” of the `do`

. It’s just syntax that will work with any monad.

One other thing to point out. Using the named functions and `>>=`

has one restricting side effect that the `do`

notation and the `bind`

notation it is derived from do not. Consider this:

```
do x <- (Just 10)
y <- if x<10 then Nothing else (Just (x-10))
z <- if (y `mod` 2)==0 then (Just (y*y)) else Nothing
(return (z+x+y))
```

where `x`

and `y`

are used later than in the original expression. If you use named functions this won’t work because of the statically scoped nature of Haskell. We’ll discuss this later, but for now just try to rewrite the last `do`

notation using the explicitly named functions and see what happens.

We have now tempted fate by trying to understand the `Monad`

instance `Maybe`

and explain the `do`

notation. Fear not. To move forward you need only understand that in the notation:

```
do m <- n
p <- q
...
return z
```

`n`

is evaluated first. If `Just x`

is returned `m`

is bound to `x`

and control moves to `p <- q`

. `q`

is evaluated and the process repeats. If `Nothing`

is ever returned, then all subsequent operations are skipped and `do`

returns `Nothing`

. So, whenever `Nothing`

results execution halts and we fall through. This is exactly what we want. A kind of exception handling where `Nothing`

represents an exception.

Let’s build some interpreters!