This lec­ture is adjusted from Niki Vazou.

Author’s note: Despite instill­ing fear in new Haskell pro­gram­mers every­where, mon­ads are really not that scary. If you have a good grasp of applica­tives and func­tors, mon­ads are really just a sim­ple (but pow­er­ful) exten­sion of this idea.

## A Simple Arithmetic Evaluator

To moti­vate mon­ads, we will start by defin­ing a sim­ple arith­metic lan­guage with inte­gers and divi­sion.

```data Expr = Val Int
| Div Expr Expr
deriv­ing (Show)
```

Let’s define an eval­u­a­tor for our lan­guage.

```eval              ::  Expr -> Int
eval (Val n)     =  n
eval (Div x y)   =  eval x `div` eval y
```

Seems good. How­ever, this eval­u­a­tor does not han­dle divi­sion by zero.

```Pre­lude> eval (Div (Val 1) (Val 0))
*** Excep­tion: divide by zero
```

Let’s use the `Maybe` type to help han­dle this excep­tion.

```data Maybe a = Noth­ing | Just a
```

Now let’s define a new func­tion called `safe­Div` which per­forms the divi­sion unless the divi­sor is `0`, in which case it will sim­ply return `Noth­ing`.

```safe­Div     :: Int -> Int -> Maybe Int
safe­Div n m =  if m == 0 then Noth­ing else Just (n `div` m)
```

Ok, now let’s define a bet­ter eval­u­a­tor `eval1` that per­forms safe divi­sion.

```eval1              ::  Expr -> Maybe Int
eval1 (Val n)     =  pure n
eval1 (Div x y)   =  eval1 x `safe­Div` eval1 y
```

Hmmm, this doesn’t type­check though! `safe­div` expects two argu­ments of type int, but here we have sup­plied it with two `Maybe Ints`. Well, `Maybe` is an applica­tive func­tor, and this seems like that, so maybe we can do the fol­low­ing

```eval2              ::  Expr -> Maybe Int
eval2 (Val n)     =  pure n
eval2 (Div x y)   =  pure safe­Div <*> eval2 x <*> eval2 y
```

Nope, still doesn’t type­check! Let’s just con­sider the `pure safe­Div <*> eval2 x` part. The type sig­na­ture of `<*>` is `f (a -> b) -> f a -> f b`. We know that `eval2 x` will be of type `Maybe Int` so we know that `f` is `Maybe` and `a` is `Int`. We also know that `safe­Div` has the type `Int -> (Int -> Maybe Int)` so we can infer that `b` is the type `Int -> Maybe Int`.

Ok, now let’s con­sider this result applied to `eval2 y`. So this time we now the first argu­ment is of type `Maybe (Int -> Maybe Int)` and the sec­ond argu­ment is of type `Maybe Int`. By the type sig­na­ture of `<*>`, we’d there­fore expect a result of type `Maybe (Maybe Int)`, how­ever `eval2` expects a type `Maybe Int`.

Well, that’s annoy­ing. Let’s try again with pat­tern match­ing.

```eval3              ::  Expr -> Maybe Int
eval3 (Val n)     =  Just n
eval3 (Div x y)   =  case (eval3 x) of
Noth­ing -> Noth­ing
Just a  -> case (eval3 y) of
Noth­ing -> Noth­ing
Just b  -> a `safe­Div` b
```

This works! But boy it is ugly. And imag­ine if we needed to do case eval­u­a­tion on even more argu­ments... Let’s define a func­tion that might help sim­plify this.

```apply­Maybe   :: Maybe a -> (a -> Maybe b) -> Maybe b
apply­Maybe Noth­ing  _ = Noth­ing
apply­Maybe (Just x) f = f x
```

Ok, let’s try to define our eva­l­u­ta­tor using `apply­Maybe`.

```eval4              ::  Expr -> Maybe Int
eval4 (Val n)     =  Just n
eval4 (Div x y)   =  apply­Maybe (eval4 x) (\a ->
apply­Maybe (eval4 y) (\b ->
a `safe­Div` b
)
)
```

So what is this doing? It first per­forms `eval4 x`. If this returns `Noth­ing`, we sim­ply return `Noth­ing` and are done. If it is not, we per­form `apply­Maybe (eval4 y) (\b -> a `safe­Div` b)` where `a` is the `Just a` result from `eval4 x`. We do the same with (eval4 y) to fin­ish the eval­u­a­tion.

Huh, this seems a lot like imper­a­tive pro­gram­ming. We can imag­ine this as sim­i­lar to the fol­low­ing Java code.

```int eval4(Expr x, Expr y) {
if (x instanceof Val) return x.val;
else {
int a = eval4 x;
int b = eval4 y;
return a / b;
}
}
```

It appears as if `apply­Maybe` has given us a means for exe­cut­ing state­ments in order and prop­a­gat­ing excep­tions for­ward, just like the Java code above!

As you may have guessed, the func­tion `apply­Maybe` is a spe­cific instance of a rather use­ful abstrac­tion, bind (often denoted `>>=`). Let’s look at the Monad type­class to get a bet­ter feel for this.

```class Applica­tive m => Monad m where
(>>=)  :: m a -> (a -> m b) -> m b
return :: a -> m a
return = pure
```

Let’s first look at `return`. `return` takes an argu­ment of type `a`, and wraps it in a Monadic con­text `m`. Notice this is equiv­a­lent to `pure` from the `Applica­tive` type­class.

Now for bind (`>>=`). Notice that `bind` has the same type sig­na­ture as `apply­Maybe` from the ear­lier exam­ple, but now `Maybe` has been replaced with `m`. `bind` takes two argu­ments. The first is a value of type `a` in the monad con­text `m`. The sec­ond is a func­tion that takes a value of type `a` and returns a value of type `b` in the monad con­text `m`. The return type of `bind` is a value of type `b` in the monad con­text `m`. We can think of this func­tion as extract­ing the value of type `a` from the first argu­ment’s monadic con­text `m`, and then apply­ing the sec­ond argu­ment to that value.

The Monad instance for Maybe is exactly what we would expect from the ear­lier exam­ple.

```instance Monad Maybe where
-- return      :: a -> Maybe a
return x       =  Just x
-- (>>=)       :: Maybe a -> (a -> Maybe b) -> Maybe b
Noth­ing  >>= _ =  Noth­ing
(Just x) >>= f =  f x
```

Let’s look at the Monad instance for lists.

```instance Monad [] where
-- (>>=)  :: [a] -> (a -> [b]) -> [b]
xs >>= f = ((foldr (++) []) . map f) xs
-- return :: a -> [a]
return x = [x]
```

Let’s see a few exam­ples of this at work.

```Pre­lude> [1,2,3] >>= (\x -> [x..x+1])
[1,2,2,3,3,4]
```

So, what hap­pened here? First, `>>=` mapped our lambda func­tion onto the list, yield­ing `[[1,2], [2,3], [3,4]]` and then called `foldr (++) []` on that value which con­cate­nates the sub­lists yield­ing the result.

Ok, can we do sequenc­ing as with `Maybe`? Yes! Let’s see.

```Pre­lude> let foo x y = x >>= \a -> y >>= \b -> return (a,b)
```

What would be a good name for `foo`? `pairs`!

```Pre­lude> let pairs xs ys = xs >>= \x -> ys >>= \y -> return (x,y)
Pre­lude> pairs [1,2] [3,4]
[(1,3),(1,4),(2,3),(2,4)]
```

The func­tion first extracts each ele­ment from the list and binds it to `x`. It then extracts each ele­ment of `ys` and binds it to `y`. Finally, for each pair `x` and `y`, it com­bines them in a tuple `(x,y)` and then calls `return` on the tuple, which wraps the tuple in a list.

Hmmm, this is ok, but only if there were a nicer syn­tax... there is!

```let pairs xs ys = do x <- xs
y <- ys
return (x,y)
```

This looks like sequen­tial pro­gram­ming. What about the fol­low­ing?

```Pre­lude> pairs (Just 2) (Just 4)
Just (2,4)
```

Inter­est­ing, pairs actu­ally works for all mon­ads! What do we think will hap­pen for the fol­low­ing?

```Pre­lude> pairs (Just 2) (Noth­ing)
Noth­ing
```

Neat!