Jabberwocky

snicker-snack!

Monads for Dummies

| Comments

_note: on that topic, please read my newer blog post, which points to great tutorials

A while ago I gave a talk at jsconf.eu about functional programming. I wasn’t happy with the explanation I gave on monads. Since I feel I can do better than that, I’m going to add my blog post to the hundreds of posts already floating around on the subject, hoping that it will help some people to see things more clearly

Should you know about monads?

Strictly speaking, despite what the gurus may tell you, no. I read some blog posts from Haskell users stating that you did not need to know about monads to use them – and for Haskell monads are bread and butter (one source contradicting this a little bit). Some libraries (say IO) will take care of business for you, and you can use them without getting into intricacies of how they work. And that’s fine.

However, if, like me, you are curious and like to know what’s under the hood, you should read on.

Also, reading blog posts and listening in to conversations you get the feeling the world is split between those who understand monads, and those who don’t. I’d like to say I give a clear view of what monads are, but you still need to get your head around them – I encourage you to try some of the code examples.

What are monads?

The term monad covers both a mathematical concept from category theory and a functional programming concept. The two are losely related, I’m told, but I won’t lie: I haven’t looked at the mathematical definition. I’ll be talking about monads – the functional programming concept.

Basics: You have a data structure, and two functions, wrap (return in Haskell) and bind. I’ll explain about the 2 functions first, and then show some examples of kinds of monads.

Getting started with the Identity Monad

wrap (I like this name better than ‘return’ or ‘unit’, because it’s much more expressive), creates a monadic value from any value you feed it. What is a monadic value? It’s a function, that closes over the value you gave it.

The simplest wrap function in javascript:

1
2
3
  var wrap = function(value) {
    return function() { return value }
  };

in clojure:

1
(defn wrap[value] (fn[] value))

If you call wrap, it will return a function (the monadic value), which when called will return the original value passed in.

1
  wrap('candy')(); // => 'candy'

or

1
  ((wrap "candy")) ; => "candy"

bind will allow you to ‘bind’ a function that takes a monadic value to the monadic value. The idea is that the bind operation will take a monadic value as argument, and a function that returns a monadic value, and combine the monadic value with the function to return another monadic value. in javascript

1
2
3
  var bind = function(mv, f) {
    return f(mv());
  };

in clojure

1
  (defn bind [mv f] (f (mv)))

demonstration in JS

1
2
3
  var more = function(value) {
      return wrap("more " + value);
  }

does:

1
2
  bind(wrap('candy'), more) // function which returns a monadic value
  bind(wrap('candy'), more)() // => "more candy"

in clojure

1
2
3
(defn more[value]
    (wrap (str "more " value)))
(bind (wrap "candy") more) ; function which returns a monadic value

bind and wrap are dual, two faces of the same coin – if your wrap creates a more elaborate monadic value, then your bind must be able to handle that and pass all all the corresponding parameters (see State monad a bit lower).

To chain functions working in this way, we need functions that integrate bind and return a monadic value. A monadic version of more, integrating bind:

1
2
3
4
5
  var mMore = function(mv) {
    return bind(mv, function(value) {
      return wrap("more " + value);
    })
  }

So we could transform a ‘normal’ more function:

1
2
3
  var normalMore = function(value) {
    return "more " + value;
  }

which is what you’d use in the first place, in a monadic version using a ‘lift’ function

1
2
3
4
5
6
7
  var lift = function(f) {
    return function(mv) {
      return bind(mv, function() {
        return wrap(f(mv()));
      })
    }
  }

so that lift(normalMore) is basically equivalent to mMore. clojure version:

1
2
3
4
5
6
7
8
(defn mMore[mv]
  (bind mv (fn[value]
    (wrap (str "more " value)))))

(defn lift[f]
  (fn[mv]
    (fn[] (bind mv f))
   ))

Having ‘lifted’ functions allows us to daisy-chain operations seemlessly, because they take a monadic value and output a monadic value.

The examples so far are all built around the simplest monad of all, the Identity monad. I’ll show you a couple of other kinds of monads. The data structure of the monad basically comes down to what is enclosed by the monadic value, and whether the monadic value takes arguments – this will become clearer in the examples.

Maybe Monad

The second simplest monad is basically a variant on the identity monad, but a significant one: the bind function will not execute the function if the value is null (or equivalent), but just pass the value on. This difference is significant, because it means that a null value will not cause functions to error. Obviously, you’d only use the maybe monad if a null value was acceptable in your context. So: the wrap function is the same The bind function changes a little: in js

1
2
3
4
5
6
7
8
9
  var bind = function(mv, f) {
    return function() {
      if (mv()) {
        return f(mv())();
      } else {
        return mv();
      }
    }
  };

in clojure

1
2
3
4
5
(defn bind[mv f]
  (let [value (mv)]
    (if (nil? value)
      (wrap nil)
      (f (mv)))))

State Monad

This wiki entry: the State monad is quite different from the Maybe and the list monads, in that it doesn’t represent the result of a computation, but rather a certain property of the computation itself. What we do is model computations that depend on some internal state as functions which take a state parameter.

The State monad allows you to handle computations that depend on an internal state. The state is actually an argument of the monadic value. This means changing the data structure returned by the monad, because the state needs to be passed on, and bind function needs reflect this too.

The wrap function: note that the output is a function that takes state.

1
2
3
4
5
6
7
  var wrap = function(drink) {
    return function(sugars) {
      return {drink: drink,
              sugars: sugars};
    }
  };
  wrap('coffee')(2); // => {drink: 'coffee', sugars: 2}
1
2
3
(defn wrap[drink]
  (fn[sugars]
    {'drink drink 'sugars sugars}))

The bind function needs to handle the more complex situation.

1
2
3
4
5
6
7
8
  var bind = function(mv, f) {
    return function(sugars) {
      var value     = mv(sugars);
      var drink     = value.drink,
          newSugars = value.sugars;
      return f(drink)(newSugars);
    }
  };
1
2
3
4
5
6
  (defn bind[mv f]
    (fn[sugars]
      (let [realized  (mv sugars)
            drink     (realized 'drink)
            newSugars (realized 'sugars)]
        ((f drink) newSugars))))

We can modify the given monadic value:

1
2
3
4
  var more = function(value) {
      return wrap("more " + value);
  }
  bind(wrap('coffee'), more)(2); // => {drink: 'more coffee', sugars: 2}
1
2
3
  (defn wrap[drink]
    (fn[sugars]
      {'drink drink 'sugars sugars}))

clj

And we can also modify state, like so:

1
2
3
4
5
6
  var addSugar = function(drink) {
    return function(sugars) {
      return { drink: drink, sugars: sugars + 1 }
    }
  }
  bind(wrap('coffee'), addSugar)(2); // => {drink: 'coffee', sugars: 3}
1
2
3
4
5
6
(defn bind[mv f]
  (fn[sugars]
    (let [realized  (mv sugars)
          drink     (realized 'drink)
          newSugars (realized 'sugars)]
      ((f drink) newSugars))))

With these, you can chain operations to create a sequence of things to happen, and then feed it state (avoiding global state).

1
2
3
4
5
6
7
8
var mMore = function(mv) {
  return bind(mv, more);
}
var mAddSugar = function(mv) {
  return bind(mv, addSugar);
}

var realized = mMore(mAddSugar(mMore(mAddSugar(wrap("coffee")))))(0); // => {drink: "more more coffee", sugars: 2}
1
  ((mMore (mAddSugar (mMore (mAddSugar (wrap "coffee"))))) 0) ; => {'drink "more more coffee" 'sugars 2}

A more elegant syntax can be obtained by working with ‘pipe’ operators (see J Coglan’s post for an example for the identity case), or do-monad using the clojure monads library.

As you can see bind, wrap and the output format are all related, which is why in statically typed languages like Haskell, kinds of monads are fully fledged types of their own.

This post is already becoming a little too long, otherwise I’d like to introduce you to another interesting monad, the list monad, which allows us to do the usual list operations, but in monad style.

Monadic Laws

It’s possible that you stumbled onto monads without knowing it yourself, while working on some of your code – some blog posts seem to imply that this happens.

You can easily check whether that’s the case by checking whether your functions answer the formal definition of monads, codified in the 3 monadic laws:

  • left unit: wrap acts as neutral element of bind
1
2
bind(wrap("candy"), more) // is equivalent to
more("candy")
1
2
(bind (wrap value) f) ; is equivalent to
(f value)
  • right unit: wrap acts as neutral element of bind
1
2
bind(wrap("candy"), wrap) // is equivalent to
wrap("candy")
1
2
(bind (wrap value) wrap) ; is equivalent to
(wrap value)
  • associative: chaining bind blocks should have the same effect as nesting them
1
2
bind(bind(mv,f),g) // is equivalent to
bind(mv,function(x) { return bind(f(x),g) })
1
2
(bind (bind mv f) g) ; is equivalent to
(bind mv (fn[x] (bind (f x) g)))

These basically constitute a series of fire-proof tests to see whether you have a monad or not. With this small caveat: unless you can reduce one to the other by using refactoring or logic, equality between two functions is not that straightforward (and programming languages usually don’t let you anyway). So when you’re talking about 2 functions being equal, it means the function yields the same results for all possible values. So technically, the tests I have in my code base are woefully insufficient.

Before you give up, usually your language contains a library that will hide much of the boilerplate shown above! I showed all that code to make the basics understandable, but chances are we can bypass most of this in practice. clojure javascript and probably a few others In Haskell the syntactic sugar is just part of the language.

Good talk explaining Monads by Carin Meyer: http://www.infoq.com/presentations/Why-is-a-Monad-Like-a-Writing-Desk

James Coglan wrote some very interesting posts playing with monads in javascript: http://blog.jcoglan.com/2011/03/05/translation-from-haskell-to-javascript-of-selected-portions-of-the-best-introduction-to-monads-ive-ever-read/ http://blog.jcoglan.com/2011/03/06/monad-syntax-for-javascript/

Mentalguy was exploring the subject in Ruby in 2005 (way ahead of the curve, mind = blown, as usual): http://moonbase.rydia.net/mental/writings/programming/monads-in-ruby/00introduction.html

More importantly, what are monads for?

This was for me the hardest part to figure out. To be perfectly honest, you don’t need monads for an impure functional language. Haskell is the only pure functional language I have any acquaintance with, and there, monads are unavoidable, because they’re the only way to do IO without violating referential transparency.

However, it’s unlikely you’d ever be forced to use monads in Clojure or javascript.

Monads essentially mean you’re working with ‘boxed’ (i.e. closed over) values, which are unpacked only at the very last moment, when they’re needed.

Monads’ benefits:

  • avoid side-effects (everything is functional)
  • thread through a number of function, potentially manipulating or avoiding errors, state or debugging messages (maybe or debug monads for the last two) see this enlightening post in clojure
  • keep the sequence of events exactly what you want it to be, even if some operations are lazy

According to this blog post, monads are appropriate when you’re composing functions and you want the input to be fed into the output directly, no matter the order in which the functions are composed. Another very good blog post about their use in Haskell.

Monads are but one of the functional patterns to explore. Others on the way down the rabbit hole:

  • recursion – we all know that one. Some functional languages implement tail call optimization, which allows you to do recursion without blowing up the stack.
  • functors: a generalization of map to not just lists, but any kind of ‘container’, like trees, maybes etc
  • y-combinators – good luck googling – a fairly theoretical construct, see Jim Weirich’s presentation if you want to tie a knot in your neurons.
  • arrows, which if I understand correctly, are a generalization of monads (monads are a subset of arrows)

So there’s food for thought and learning – I’ve only started on my journey into FP land, but it’s already proving to be rewarding.

This blog post’s code is available on github – with tests included to show that I’m not bamboozling you.

Comments