Monads In Clinical Terms

Last week, we briefly discussed Monads. If you haven’t read that post, it would probably be helpful to do so now. To recap, I talked about two things. First and foremost I talked about how monads are horrific and terrifying. Secondly I talked about the use of the bind operator, and do notation in Haskell.

Today I’ll be discussing at a very low level, what exactly a Monad is. I feel that there is a general notion that all Monads are similar to each other, and serve some common purpose. I know this has been causing issues for me. However, I’m slowly coming around to the idea that they really aren’t. Let’s consider some of the monads in Haskell. We have:

  • The List monad, which is a data structure.
  • The Maybe monad, which represents the result of a calculation that may have failed.
  • The Either monad, which represents a value, or an error.

I know what you may be thinking: “These all look like data structures!” I had this same thought, but let’s look at some more monads:

  • The IO monad, which represents some communication with the “outside world”.
  • The Writer monad, which represents logging.
  • The State monad, which represents program state.

…and then that notion falls apart. If you tried really hard, you might make a case that these are all data structures. However, they’re really not. So, what exactly is a monad? At the very basic level, a monad is two functions, and three laws. Let’s take a look at these.

Two Functions

I touched on this a bit last week, but in order for something to be a monad, it must implement two functions: bind and return. Let’s take a look at these.

Bind

Any monad typically contains a value, and some “decoration”. Bind takes a monad, a function that takes a value and returns a monad, calls that function on the value contained in the old monad, returning a new monad. Finally the logic contained within the bind function “reconciles” the old monad and new monad’s decorations, returning the final resulting monad. Conceptually, this looks something like this:

conceptual_monad

Let’s take a look at Haskell’s bind operator’s function signature:

(>>=) :: m a -> (a -> m b) -> m b

In Haskell, bind is implemented as an operator: >>=. This takes a monad containing an “a“, a function that takes an “a“, and returns a monad containing a “b“, and finally returns a monad containing a “b“. It is up to the author of a monad to determine what it means to “reconcile the decoration” taking into account the laws I’m going to talk about in a minute.

return

Compared to bind, return is child’s play. Simply put, return takes a value, and creates a new monad with the most basic amount of decoration to still be valid. This is functionally equivalent to the pure function provided by Applicative Functors.

Three Laws

While you can make any old thing a member of the Monad typeclass, it’s not actually a monad unless it obeys the law. There are three properties that a monad must satisfy in order to be a valid monad:

Left identity

Formally defined as:

return a >>= k == k a

This law states that calling return on some value, and then binding the resulting monad to some function should have the same result as just calling that function on the value. The idea here is that if return truly gives a value minimal decoration, that this decoration should not change the resulting monad of a function when bound. Let’s see how Maybe satisfies this law. Here is Maybe‘s instance definition:

instance Monad Maybe where (Just x) >>= k = k x Nothing >>= _ = Nothing return k = Just k

When Maybe‘s return implementation is called, it wraps the argument in a Just. Maybe has two bind implementations, one for Just and one for Nothing. If a Just is bound to a function, the function will be called on the value contained in the Just, and the resulting Maybe is the result of the bind function. Therefore, if the function returns a Just, bind returns that Just. If the function returns Nothing, then bind returns that Nothing.

As you can see, return always returns Just k, therefore Maybe satisfies the law of Left Identity.

Right Identity

Formally defined as:

m >>= return == m

return is a function that takes a value, and returns a monad. However, return is only supposed to just wrap the value in a minimal monad. Therefore, the monad created by return should have no affect on the “decoration reconciliation” performed by bind. Let’s see how this works with Maybe.

As you can see from the implementation posted above, Maybe has two bind implementations: one for Just, and one for Nothing. If Nothing is bound to any function, the result is automatically Nothing. If Just k is bound to a function, the result is the result of the function call. The result of Maybe‘s return function is to wrap the value in a Just. Therefore, for both bind implementations, the law holds.

Associativity

Formally defined as:

m >>= (\x -> k x >>= h) == (m >>= k) >>= h

At first this one seems complicated, but it’s really not. First, we need to understand what the word “Associativity” Means. In math, the Associative Property is a property of certain binary operations. If an operation is associative, then it does not matter how the numbers are nested, the result will be the same.

Addition is associative:

(2 + 3) + 4 = 9 2 + (3 + 4) = 9

…however subtraction is not associative:

(2 - 3) - 4 = -5 2 - (3 - 4) = 3

Simply put, bind must behave like addition, and not subtraction with regards to how it can be nested.

When You Put It Like That…

Doesn’t seem so complicated now, does it? Did all that make sense to you? Congratulations, you get monads! Now, the hard part is figuring out how to use some of the crazy monads that come in Haskell’s standard library. This is a subject I hope to help with over the coming months.

However, for the time being if you have a data type, and you can implement bind and return in a way that obeys the monad laws, then your type is a monad. Don’t let anybody tell you otherwise!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: