Something You Must Know Before Learning Monad

There is a saying goes that "Monad has a curse that when someone learns what monads are and how to use them, they lose the ability to explain it to other people."

I would like to say it is true, at least for most of the normal people. The reason is that you probably need sufficient background knowledge in order to fully (or better) understand Monad.

So how much on earth you should know before learning Monads? Why not take a look at my story first.

My Story of learning Monad

The first time I heard Monad is around November 2013 in one of my Computer Science graduate class, when we were learning some very basic category theory at that time.

Out of curiosity, I searched Google and Youtube for help. Like what you probably did already, I watched three most popular videos talking about Monad. Sadly, though I had some blurry vision of Monad, I still can't understand it. However, after truly understand Monad, I finally find out why these videos do not make much sense to me at that time, and I would like to give some comments to these three videos:

• Brian Beckman: Don't fear the Monad. In this video, Brian tries to illustrate Monad without mention any background knowledge. The good part of this video is that I can understand what he is say, but the bad part is that I really can only understand what he is saying, but I don't know what is Monad in practice, why we need monad and how it works.
• Douglas Crockford: Monads and Gonads. The main reason for me to dislike this video might be I don't use Javascript much, so I don't know what he is talking about.
• Dustin Getz: Monads for Normal People In this video, Dustin uses python to explain Monad and it makes things a lot easier for me to understand. The bad side is that he jumped into deep topic too soon before summarizing the real definition of Monad, and the example he used does not make too much sense in the realm of python.

In this semester, I took the programming language class (taught by William Cook), and we covered Haskell, Lambda Calculus and Type System. Then after reading this paper I finally understand what Monad is.

Therefore, based on my experience, you probably need the learning the following stuff first in this order before proceed:

1. Lambda Calculus. (Untyped Lambda Calculus is enough, here is a good tutorial)
2. Haskell. (Best tutorial ever: Learn you a Haskell for Great Good)
3. *Category Theory (Category Theory for Computing Science) and Type System (B.C.Pierce). These two are optional, without these knowledge you can still understand Monad with no problem.

1. Motivation / Problem

Before talking about what is Monad, we must understand what problem we are facing such that we need Monad to solve this problem.

Let fix our scenario to a pure functional programming language (We will use Haskell in examples). First recall that a functional programming language is pure if it does not have side effect (i.e., mutable state, exception handling, IO, etc.). Now, suppose we want to implement a simple evaluator:

data Exp = Con Double | Div Exp Exp

eval :: Exp -> Double
eval (Con x) = x
eval (Div x y) = eval x / eval y

An expression Exp is either a constant Con x where x is a double value, Div x y where x and y are expressions. The function eval takes an expression as input and output a double. If the expression is a constant, then the constant is returned. Otherwise (input Exp is Div), then its subterms are evaluated and the division computed.

valid = eval(Div (Div (Con 42) (Con 24)) (Con 10))
exception = eval(Div (Con 5) (Con 0))

Let's take a look at the running examples above. If we call function valid, it should compute ((42/24)/10) and yields the value of 0.175. However, if we call function exception, then it is an error: 0 should not appear on the denominator. (Note that Haskell won't crash here and will return Infinity, but let's suppose we don't want the Infinity result, we want to throw some exception message to user).

In pure functional programming language like Haskell, there is no stuff such as try...catch block to handle exceptions. However, exception handling can be mimicked by introducing a type to represent computation that may raise an exception.

data M x = Exception String | Valid x

A value of type M x either has the form Exception e, where e is an exception message string, or Valid x, where x is a value of type x.

In a straightforward but tedious way, we can change the evaluator to:

eval :: Exp -> M Double
eval (Con x) = Valid x
eval (Div x y) = case eval x of
                   Exception e -> Exception e
                   Valid x -> case eval y of
                                Exception e -> Exception e
                                Valid y ->
                                    if y == 0
                                      then Exception "divide by zero"
                                      else Valid (x/y)

Now we successfully handled "divide by zero" exception by introducing a new type M x, where x is the type variable in Haskell. Note that actually we've changed the return type of function eval, in order to mimick exceptions.

Unfortunately, we now encounter a new problem which is very common in the aspect of software engineering. That is the validation logic appears every in the business logic, we have to check the form of the result at each call of the evaluator function eval.

2. Solution / Monad

Thus, in order to make our business logic more pure, we must refactor it (i.e., use Monad). You might already have a sense that Monad can be roughly viewed as a design pattern. Moreover, it is a data structure which wrap the original value and store some additional information.

Formally, a Monad is a triple (M,unit,bind), consisting of a type constructor M and two operations of the given polymorphic types. (Note that these operations must satisfy three laws, you can find more detail description in Brian's video). Monad can also have some other helper functions.

data M x = Exception String | Valid x

unit :: a -> M a
unit x = Valid x

bind :: M a -> (a -> M b) -> M b
bind v f = case v of
             Exception e -> Exception e
             Valid x -> f x

raise :: String -> M a
raise e = Exception e

The unit function wrap the original value x into a Monad, then return the monadic value M x. The bind function takes two arguments as input: 1) v is monadic value which can be evaluate to a value, 2) f is a function which takes the original value as input and output the result wrapped in a Monad. Then the whole bind function returns the Monadic result M b. The raise function is a helper function which help use generate a exception.

eval :: Exp -> M Double
eval (Con x) = unit x
eval (Div x y) = bind (eval x) (\a->bind (eval y) (\b->if b == 0 then raise "divide by zero" else unit(a/b)))

Now you can either return value or exception in eval function, and in eval function we hide all the validation operation every time we call eval.

In convention we write the bind operation bind(v f) in this way v >>= f, and ">>=" is called the bind operator. Then we could rewrite eval (Div x y) to: eval(Div x y) = eval x >>= \a.eval y >>= \b.if b == 0 then raise "divide by zero" else unit(a/b)

So till now, what is Monad? Monad is a design pattern, which is implemented by a data structure, i.e. a truple (M,unit,bind). M is the type constructor, unit,bind are two functions (operations), which obay three laws. We can use Monad to introduce side effect and seperate the side effect with pure functional code.

The complete code can be found here.

Acknowledgement:

This article is my learning notes of course CS386L Programming Languages (Spring 2014), lectured by Prof. William Cook.