Tags

, , ,

What are Monads? Who cares? Only mathematicians and theoretical computer scientists need to concern themselves with that question. Too many words have been written in a futile attempt to “explain” Monads to programmers. The correct questions for a working programmer to ask are: What are Monads good for and how can I use Monads in my own code? And the way to answer these question is to give examples – lots of examples. Wadler’s paper on Monads for functional programming explains Monads via examples. The problem is you can’t actually run those examples in Haskell and the organization and lack of details leave something to be desired so I’m going to redo his examples , adding more details and reorganizing the presentation in order to make the explanations more clear .

His first example is exception handling. Since you’re reading about monads I assume you understand exception handling and can figure out what this code is doing.

data Term = Con Float | (Div Term Term) deriving (Show)
data M a = Raise Exception | Return a deriving (Show) 
type Exception = String

eval (Con a) = Return a
eval (Div t u) = 
  case (eval t) of
    Raise e -> Raise e
    Return a -> 
      case (eval u ) of
        Raise e -> Raise e
        Return b -> 
          if b == 0 
            then Raise "divide by zero"
            else Return (a/b)

Using Monads we will be able to write the definition of eval as

eval (Con a) = Return a
eval (Div t u) = 
  do
    a <- eval t
    b <- eval u
    if b == 0 
      then Raise "divide by zero"
      else return (a/b)

This example gives a first cut answer to the question: What Monads are good for? The second version of the code is arguably more succinct, more modular and more extensible. The ugly sequence of nested case statements has been transformed into a nice sequence of what are apparently “assignment” statements. The case block has somehow been hidden in this <- operator. If we want to change the functionality of our case we simply have to change the definition of the <- instead of changing every place in the code where the case block occurs.

We have to understand how to make this transformation. The transformation seems almost like a magic trick, but I will show you step by step how the trick is done and how you can do it too.

The key step is to encapsulate the case block into a function which we’ll call bind . Then we can rewrite eval as a sequence of nested bind calls. How does this help? This sequence of bind function calls represents a design pattern that we can encapsulate into a Monad. If we then make the M data type an instance of the Monad class and make the bind a method of this monad class we will be able to use the do notation as a more readable substitute for the sequence of bind function calls.

How do we write the bind function? The case block takes an M type value and looks at the value in the M type. If the value is Return a it does further processing on the a value. So our bind function should take as arguments the M type value and a function to process the Return value of that M type value. So we can write bind as follows.

  bind mType processValueFunction = 
          case mType of
            Raise e ->  Raise e
            Return mTypeValue   ->  processValueFunction mTypeValue

How can we rewrite the eval function using this bind function? We’ll work our way from innermost case block to outermost.

The innermost case block is

 case (eval u) of
        Raise e -> Raise e
        Return b -> 
          if b == 0 
            then Raise "divide by zero"
            else Return (a/b)

Its clear mType in the definition of the bind function is eval u

But what is processValueFunction ? We have to write

if b == 0 
   then Raise "divide by zero"
   else Return (a/b)

as a function applied to b.

Clearly the above code is equivalent to the following function call:

(\b -> 
  if b == 0 
    then Raise "divide by zero" 
    else Return (a/b) ) b

Note that I made the name of the function argument the same as the variable to which the function is being applied, namely b This is perfectly legitimate. Function argument names are completely arbitrary and don’t conflict with the names of the variables to which the function is applied.

So we can rewrite the case block as:

 case (eval u) of
        Raise e -> Raise e
        Return b -> 
          (\b ->if b == 0 
                  then Raise "divide by zero"
                  else Return (a/b)) b

Finally we can rewrite the case block using bind as follows:
and because this step is so important I’ll also repeat the case block and the definition of bind.

 bind (eval  u) 
  (\b ->
   if b == 0 
    then Raise "divide by zero" 
    else Return (a/b) )

--------------------------------------------------------
 case (eval u) of
        Raise e -> Raise e
        Return b -> 
          if b == 0 
            then Raise "divide by zero"
            else Return (a/b)
--------------------------------------------------------
 bind mType processValueFunction = 
          case mType of
            Raise e ->  Raise e
            Return mTypeValue   ->  processValueFunction mTypeValue

This is the key step! Make you sure you understand how bind is equivalent to the case.This is the key step! Make you sure you understand how bind is equivalent to the case. Sic! I just wanted to repeat myself for emphasis.

Putting bind into the original function we get:

eval (Div t u) =
 case (eval t) of
   Raise e -> Raise e
   Return a  ->  
    bind (eval  u) 
     (\b ->
       if b == 0 
         then Raise "divide by zero" 
         else Return (a/b) )

Let’s convert the top most case block to a bind function call.

This time the M type is (eval t).
We have to rewrite the following:

 bind (eval  u) 
     (\b ->
       if b == 0 
         then Raise "divide by zero" 
         else Return (a/b) )

as a function applied to a
We see that in this case that following function call is equivalent .

(\a ->  
   bind (eval  u) 
        (\b -> 
          if b == 0 
           then Raise "divide by zero" 
           else Return (a/b) ) a

So we can rewrite our eval function as:

eval (Div t u) = 
 bind (eval t) 
      (\a ->
        bind (eval u) 
             (\b -> 
                 if b == 0 
                   then Raise "divide by zero" 
                   else Return (a/b) )

Now let’s rename bind to >>= and make it an infix operator. Then we can rewrite our code as

eval (Div t u) = 
  (eval t) >>=
      (\a ->
         (eval u) >>=
             (\b -> 
                 if b == 0 
                   then Raise "divide by zero" 
                   else Return (a/b) ))

Let’s reformat this slightly and remove unnecessary parenthesis.

eval (Div t u) = 
  (eval t) >>= \a ->
  (eval u) >>= \b -> 
                 if b == 0 
                   then Raise "divide by zero" 
                   else Return (a/b) 

We’ve done it. We’ve converted the nested series of case statements into a nested sequence of function calls. You should already be able to see in the above code the outlines of the following code to which we’re aiming.

eval (Con a) = Return a
eval (Div t u) = 
  do
    a <- eval t
    b <- eval u
    if b == 0 
      then Raise "divide by zero"
      else return (a/b)

The final step is to make the M data type an instance of the Monad class and make the >>= function a method of this monad. We also need to a return function because…

instance Monad M
  where
   (>>=) mType processValueFunction = 
          case mType of
            Raise e ->  Raise e
            Return mTypeValue   ->  processValueFunction mTypeValue
   return mTypeValue = Return  mTypeValue

Finally we can use the do construct to write our nested sequence of bind functions calls as just a series of assignments. The do construct is a short hand for sequencing the bind function.

 do p1 <- e1
    some expression involving p1

is the same as

  e1 >>= \p1 -> some expression involving p1

We said our function could be written in this do notation as:

eval  (Div t u) = 
  do
    a <- eval t
    b <- eval u
    if b == 0 
      then Raise "divide by zero"
      else return (a/b)

Let’s unwrap this and try to make it look like the version using >>=

Expanding the first <- gives

    eval t >>= \a -> 
     b <- eval u
     if b == 0 
      then Raise "divide by zero"
      else return (a/b)

Expanding the second <- gives

    eval t >>= \a -> 
    eval u >>= \b ->
      if b == 0 
       then Raise "divide by zero"
       else return (a/b)

Which shows that thes sequence of bind calls is equivalent to the series of <- in the do construct.

Advertisements