Monads

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.

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!