Broken Brains and Other Monad Debris

With apologies to David Chess and Danny Hillis.

One afternoon a student said “Roshi, I don’t really understand what’s going on. I mean, we sit in zazen and we gassho to each other and everything, and Felicia got enlightened when the bottom fell out of her water-bucket, and Todd got enlightened when you popped him one with your staff, and people work on koans and get enlightened, but I’ve been doing this for two years now, and the koans don’t make any sense, and I don’t feel enlightened at all! Can you just tell me what’s going on?”

“Well you see,” Roshi replied, “for most people, and especially for most educated people like you and I, what we perceive and experience is heavily mediated, through language and concepts that are deeply ingrained in our ways of thinking and feeling. Our objective here is to induce in ourselves and in each other a psychological state that involves the unmediated experience of the world, because we believe that that state has certain desirable properties. It’s impossible in general to reach that state through any particular form or method, since forms and methods are themselves examples of the mediators that we are trying to avoid. So we employ a variety of ad hoc means, some linguistic like koans and some non-linguistic like zazen, in hopes that for any given student one or more of our methods will, in whatever way, engender the condition of non-mediated experience that is our goal. And since even thinking in terms of mediators and goals tends to reinforce our undesirable dependency on concepts, we actively discourage exactly this kind of analytical discourse.”

And the student was enlightened.

One thing that I’ve been doing throughout the past few weeks of Hacker School is asking various likely-seeming people to explain monads. My hope has been that, like in David Chess’s koan above, eventually I’ll happen across some method that has a short enough inferential distance for me to understand. Almost every explanation has left me thinking “Okay, that made sense, but I have no idea how it relates to any of the other descriptions of monads that I’ve heard so far.” Which of course puts me in mind of another classic hacker koan:

A novice was trying to fix a broken Lisp machine by turning the power off and on.

Knight, seeing what the student was doing, spoke sternly: “You cannot fix a machine by just power-cycling it with no understanding of what is going wrong.”

Knight turned the machine off and on.

The machine worked.

Yesterday, Lindsey Kuper linked to this paper, and the bottom fell out of my water-bucket.

Here’s how it works.

Functions output things. You can categorize functions by the kind of thing they output. Boolean functions output “True” or “False”. Integer functions output integers. And monadic functions output monads. It’s easy to tell if a function is boolean - we just look at it, and see whether it has possible output values other than “True” and “False”. But if we don’t know what a monad is, how can we tell if a function is monadic?

Monads follow three laws, without exception. These laws are as follows:

  1. A monad shall not harm a human, nor, through inaction, allow a human to come to harm. …wait, those are the wrong Three Laws. Let’s try that again.

A thing is a monad if, for every possible function that outputs that kind of thing, these three laws hold true:

  1. Left Identity: return >=> f ≡ f
  2. Right Identity: f >=> return ≡ f
  3. Associativity: (f >=> g) >=> h ≡ f >=> (g >=> h)

(If this looks like gibberish, bear with me for a moment.)

Return is a function that takes a thing and makes a monad version of the thing. If, for example, your monad is a wallet, then return $20 returns a wallet containing $20.

f, g, and h are functions that return this kind of monad. They could be anything, and the monad laws wouldn’t care. Speaking again of our monadic wallet, perhaps f takes an ATM card and puts $40 in your wallet.

>=> is the monad version of compose. It takes two monadic functions (e.g. f and g) and sticks them together to make a third monadic function (e.g. h). Let’s say g is a function that takes some amount of US dollars, exchanges them for Canadian dollars, and puts the Canadian dollars in your wallet. Then f >=> g produces h: a function that takes your ATM card and gives you back a wallet holding $44.87 CAD (at today’s exchange rates, anyway).

In terms of type signatures,

  • f a :: Monad m => a -> m b
  • return a :: Monad m => a -> m b
  • (>=>) :: Monad m => (a -> m b) -> (b -> m c) -> a -> m c

So now we’re ready to look at the monad laws again. And they’re actually pretty intuitive, if you don’t fret about the notation. The first two laws say that return and monadic-function-compose cancel eachother out. That’s it. If return is one of the arguments to >=>, then the result is just the other argument.

The third law says that when we’re chaining together monadic functions with >=>, order of evaluation doesn’t matter.

That’s all a monad has to be. Anything that satisfies these three laws for all possible f (and g, and h) is a monad. We have grokked the monad-nature. You may see these laws expressed in other ways - with different notation, or different basic operations - but these formulations are all equivalent.

The obvious next question: So why does anyone care?

Well, note that we haven’t defined a way to get the value back OUT of the monad. This seems confusing - if I wanted a wallet that I could never take anything back out of, I’d just use Mt. Gox! But actually, this is quite useful, and here’s why: As long as we interact with a monad only through the operations listed above, it’s a valid purely-functional construct. Our pure code can handle wallet-objects just fine, and rely on the guarantee that f functions f, g, and h will always give us a wallet. In this way our program remains deterministic, which is good.

But what if your bank account is overdrafted, and the ATM refuses to give you any money? What if the currency exchanges are not open because the US has declared war on Canada so that Halliburton can extract their delicious, delicious maple syrup? Then things begin to go wrong, and our WalletMonad must account for this internally. In other words, our WalletMonad is impure - it both depends on and alters the external state of the world. But in doing so, it insulates the rest of a pure functional program from those side effects. Monads as they are used in Haskell and other functional programming languages are very much like Jack Nicholson’s character in A Few Good Men:

Son, we live in a world that has walls, and those walls have to be guarded by men with guns. Who’s gonna do it? You? You, Lieutenant Weinberg? I have a greater responsibility than you can possibly fathom. You weep for Santiago and you curse the Marines. You have that luxury. You have the luxury of not knowing what I know, that Santiago’s death, while tragic, probably saved lives. And my existence, while grotesque and incomprehensible to you, saves lives!

To paraphrase a line commonly misattributed to George Orwell, we execute safely in our functional pipelines because rough monads stand ready in the night to visit violence on those who would segfault us.

If you’ve just started seeing monads everywhere you look, I’m glad; hopefully that means I’m not crazy.