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!