Of Love and Monads

I didn’t mean to entirely dismiss the question of what Monads are. My objection is that some Monad tutorials launch into vague, abstract definitions and analogies before the reader has had the chance to see an example of a Monad.

To make an analogy of my own, (or is it a simile?) , trying to define Monads to someone who had never seen or used them is like trying to define “Love” to someone who had never experienced that sublime emotion. Your definition could only give the vaguest, the most simplistic, the will-o-the wispest idea of what love is and your poor, lonely reader would be as confused as the readers of most Monads tutorials. No, the best way to explain Love to a such a person is to have her experience it for herself. Armed with that experience she would be able to create her own definition. She would no longer need you to provide one.

And so it is with Monads and so it is with this blog. I want to give you the experience of Monadic bliss to allow you to come up with your own definition. But, after having had that experience, you may find that an explicit definition is no longer necessary – that concrete experience is better than an abstract definition. A definition provides cold comfort on a dark stormy night, but an experience! — that’s something that you can cuddle up with and that will keep you warm when it is a cold rainy night in your soul.

Perhaps you will be moved to write your own Monad tutorial or better yet you might try to get out more on Saturday nights and experience a little love yourself.

Advertisements

Monads By Example: Exception Handling

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.