# Monads

This lecture is adjusted from Niki Vazou.

Author’s note: Despite instilling fear in new Haskell programmers everywhere, monads are really not that scary. If you have a good grasp of applicatives and functors, monads are really just a simple (but powerful) extension of this idea.

## A Simple Arithmetic Evaluator

To motivate monads, we will start by defining a simple arithmetic language with integers and division.

data Expr = Val Int | Div Expr Expr deriving (Show)

Let’s define an evaluator for our language.

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

Seems good. However, this evaluator does not handle division by zero.

Prelude> eval (Div (Val 1) (Val 0)) *** Exception: divide by zero

Let’s use the `Maybe`

type to help handle this exception.

data Maybe a = Nothing | Just a

Now let’s define a new function called `safeDiv`

which performs the division unless the divisor is `0`

, in which case it will simply return `Nothing`

.

safeDiv :: Int -> Int -> Maybe Int safeDiv n m = if m == 0 then Nothing else Just (n `div` m)

Ok, now let’s define a better evaluator `eval1`

that performs safe division.

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

Hmmm, this doesn’t typecheck though! `safediv`

expects two arguments of type int, but here we have supplied it with two `Maybe Ints`

. Well, `Maybe`

is an applicative functor, and this seems like that, so maybe we can do the following

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

Nope, still doesn’t typecheck! Let’s just consider the `pure safeDiv <*> eval2 x`

part. The type signature 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 `safeDiv`

has the type `Int -> (Int -> Maybe Int)`

so we can infer that `b`

is the type `Int -> Maybe Int`

.

Ok, now let’s consider this result applied to `eval2 y`

. So this time we now the first argument is of type `Maybe (Int -> Maybe Int)`

and the second argument is of type `Maybe Int`

. By the type signature of `<*>`

, we’d therefore expect a result of type `Maybe (Maybe Int)`

, however `eval2`

expects a type `Maybe Int`

.

Well, that’s annoying. Let’s try again with pattern matching.

eval3 :: Expr -> Maybe Int eval3 (Val n) = Just n eval3 (Div x y) = case (eval3 x) of Nothing -> Nothing Just a -> case (eval3 y) of Nothing -> Nothing Just b -> a `safeDiv` b

This works! But boy it is ugly. And imagine if we needed to do case evaluation on even more arguments... Let’s define a function that might help simplify this.

applyMaybe :: Maybe a -> (a -> Maybe b) -> Maybe b applyMaybe Nothing _ = Nothing applyMaybe (Just x) f = f x

Ok, let’s try to define our evalutator using `applyMaybe`

.

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

So what is this doing? It first performs `eval4 x`

. If this returns `Nothing`

, we simply return `Nothing`

and are done. If it is not, we perform `applyMaybe (eval4 y) (\b -> a `

safeDiv` b)`

where `a`

is the `Just a`

result from `eval4 x`

. We do the same with (eval4 y) to finish the evaluation.

Huh, this seems a lot like imperative programming. We can imagine this as similar to the following 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 `applyMaybe`

has given us a means for executing statements in order and propagating exceptions forward, just like the Java code above!

## The Monad Typeclass

As you may have guessed, the function `applyMaybe`

is a specific instance of a rather useful abstraction, bind (often denoted `>>=`

). Let’s look at the Monad typeclass to get a better feel for this.

class Applicative 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 argument of type `a`

, and wraps it in a Monadic context `m`

. Notice this is equivalent to `pure`

from the `Applicative`

typeclass.

Now for bind (`>>=`

). Notice that `bind`

has the same type signature as `applyMaybe`

from the earlier example, but now `Maybe`

has been replaced with `m`

. `bind`

takes two arguments. The first is a value of type `a`

in the monad context `m`

. The second is a function that takes a value of type `a`

and returns a value of type `b`

in the monad context `m`

. The return type of `bind`

is a value of type `b`

in the monad context `m`

. We can think of this function as extracting the value of type `a`

from the first argument’s monadic context `m`

, and then applying the second argument to that value.

The Monad instance for Maybe is exactly what we would expect from the earlier example.

instance Monad Maybe where -- return :: a -> Maybe a return x = Just x -- (>>=) :: Maybe a -> (a -> Maybe b) -> Maybe b Nothing >>= _ = Nothing (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 examples of this at work.

Prelude> [1,2,3] >>= (\x -> [x..x+1]) [1,2,2,3,3,4]

So, what happened here? First, `>>=`

mapped our lambda function onto the list, yielding `[[1,2], [2,3], [3,4]]`

and then called `foldr (++) []`

on that value which concatenates the sublists yielding the result.

Ok, can we do sequencing as with `Maybe`

? Yes! Let’s see.

Prelude> let foo x y = x >>= \a -> y >>= \b -> return (a,b)

What would be a good name for `foo`

? `pairs`

!

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

The function first extracts each element from the list and binds it to `x`

. It then extracts each element of `ys`

and binds it to `y`

. Finally, for each pair `x`

and `y`

, it combines 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 syntax... there is!

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

This looks like sequential programming. What about the following?

Prelude> pairs (Just 2) (Just 4) Just (2,4)

Interesting, pairs actually works for all monads! What do we think will happen for the following?

Prelude> pairs (Just 2) (Nothing) Nothing

Neat!