Translation from Haskell to JavaScript of selected portions of the best introduction to monads I’ve ever read

(With apologies to John Gruber and A Neighborhood of Infinity.)

I know, I know, the world does not need yet another introduction to monads (or yet another article complaining that world does not need yet another introduction to monads). So you’ll be glad to know this isn’t one of those, in the sense that it’s not new. I thought I’d write it because, first, monads are worth knowing about, and second, because I want to get into how they relate to asynchronous programming and I want a baseline in JavaScript to help explain things I might write later. It’s also a valuable exercise in thinking in terms of types. If you’re fine reading a little Haskell, I highly recommend you read the original article, You Could Have Invented Monads (And Maybe You Already Have).

First up, a little back story. Monads are more prevalent in Haskell because it only allows pure functions, that is functions that do not have side effects. Pure functions accept input as arguments and emit output as return values, and that’s it. The languages I typically use (Ruby and JavaScript) do not have this constraint, but it often turns out to be a useful discipline to enforce yourself. The typical monad introduction will tell you that monads are all about sneaking side effects into this model so you can do I/O, but that’s just one application. Monads are really about composing functions, as we’ll see.

Let’s consider an example. Suppose you have a function for finding the sine of a number, which in JavaScript would be a simple wrapper around the Math library:

var sine = function(x) { return Math.sin(x) };

And you have another function for taking the cube of a number:

var cube = function(x) { return x * x * x };

These functions take one number as input and return one number as output, making them composable: you can use the output of one as the input to the next:

var sineCubed = cube(sine(x));

Let’s create a function to encapsulate function composition. This takes two functions f and g and returns another function that computes f(g(x)).

var compose = function(f, g) {
  return function(x) {
    return f(g(x));
  };
};

var sineOfCube = compose(sine, cube);
var y = sineOfCube(x);

Next we decide that we need to debug these functions, and we want to log the fact that they have been called. We might do this like so:

var cube = function(x) {
  console.log('cube was called.');
  return x * x * x;
};

But we’re not allowed to do this in a system that only allows pure functions: console.log() is neither an argument nor a return value of the function, it is a side effect. If we want to capture this logging information, it must form part of the return value. Let’s modify our functions to return a pair of values: the result, and some debugging information:

var sine = function(x) {
  return [Math.sin(x), 'sine was called.'];
};

var cube = function(x) {
  return [x * x * x, 'cube was called.'];
};

But we now find, to our horror, that these functions don’t compose:

cube(3) // -> [27, 'cube was called.']
compose(sine, cube)(3) // -> [NaN, 'sine was called.']

This is broken in two ways: sine is trying to calculate the sine of an array, which results in NaN, and we’re losing the debugging information from the call to cube. We’d expect the composition of these functions to return the sine of the cube of x, and a string stating that both cube and sine were called:

compose(sine, cube)(3)
// -> [0.956, 'cube was called.sine was called.']

A simple composition won’t work here because the return type of cube (an array) is not the same as the argument type to sine (a number). A little more glue is required. We could write a function to compose these ‘debuggable’ functions: it would break up the return values of each function and stitch them back together in a meaningful way:

var composeDebuggable = function(f, g) {
  return function(x) {
    var gx = g(x),      // e.g. cube(3) -> [27, 'cube was called.']
        y  = gx[0],     //                 27
        s  = gx[1],     //                 'cube was called.'
        fy = f(y),      //     sine(27) -> [0.956, 'sine was called.']
        z  = fy[0],     //                 0.956
        t  = fy[1];     //                 'sine was called.'
    
    return [z, s + t];
  };
};

composeDebuggable(sine, cube)(3)
// -> [0.956, 'cube was called.sine was called.']

We’ve composed two functions that take a number and return a number+string pair, and created another function with the same signature, meaning it can be composed further with other debuggable functions.

To simplify things, I’m going to need to borrow some Haskell notation. The following type signature says that the function cube accepts a number and returns a tuple containing a number and a string:

cube :: Number -> (Number,String)

This is the signature that all our debuggable functions and their compositions have. Our original functions had the simpler signature Number -> Number; the symmetry of the argument and return types is what makes these functions composable. Rather than writing customized composition logic for our debuggable functions, what if we could simply convert them such that their signature was:

cube :: (Number,String) -> (Number,String)

We could then use our original compose function for glueing them together. We could do this conversion by hand, and rewrite the source for cube and sine to accept (Number,String) instead of just Number but this doesn’t scale, and you end up writing the same boilerplate in all your functions. Far better to let each function just do its job, and provide one tool to coerce the functions into the desired format. We’ll call this tool bind, and its job is to take a Number -> (Number,String) function and return a (Number,String) -> (Number,String) function.

var bind = function(f) {
  return function(tuple) {
    var x  = tuple[0],
        s  = tuple[1],
        fx = f(x),
        y  = fx[0],
        t  = fx[1];
    
    return [y, s + t];
  };
};

We can use this to convert our functions to have composable signatures, and then compose the results.

var f = compose(bind(sine), bind(cube));
f([3, '']) // -> [0.956, 'cube was called.sine was called.']

But now all the functions we’re working with take (Number,String) as their argument, and we’d much rather just pass a Number. As well as converting functions, we need a way of converting values to acceptable types, that is we need the following function:

unit :: Number -> (Number,String)

The role of unit is to take a value and wrap it in a basic container that the functions we’re working with can consume. For our debuggable functions, this just means pairing the number with a blank string:

// unit :: Number -> (Number,String)
var unit = function(x) { return [x, ''] };

var f = compose(bind(sine), bind(cube));
f(unit(3)) // -> [0.956, 'cube was called.sine was called.']

// or ...
compose(f, unit)(3) // -> [0.956, 'cube was called.sine was called.']

This unit function also lets us convert any function into a debuggable one, by converting its return value into an acceptable input for debuggable functions:

// round :: Number -> Number
var round = function(x) { return Math.round(x) };

// roundDebug :: Number -> (Number,String)
var roundDebug = function(x) { return unit(round(x)) };

Again, this type of conversion, from a ‘plain’ function to a debuggable one, can be abstracted into a function we’ll call lift. The type signature says that lift takes a function with signature Number -> Number and returns a function with signature Number -> (Number,String)

// lift :: (Number -> Number) -> (Number -> (Number,String))
var lift = function(f) {
  return function(x) {
    return unit(f(x));
  };
};

// or, more simply:
var lift = function(f) { return compose(unit, f) };

Let’s try this out with our existing functions and see if it works:

var round = function(x) { return Math.round(x) };

var roundDebug = lift(round);

var f = compose(bind(roundDebug), bind(sine));
f(unit(27)) // -> [1, 'sine was called.']

We’ve discovered three important abstractions for glueing debuggable functions together:

  • lift, which converts a ‘simple’ function into a debuggable function
  • bind, which converts a debuggable function into a composable form
  • unit, which converts a simple value into the format required for debugging, by placing it in a container

These abstractions (well, really just bind and unit), define a monad. In the Haskell standard library it’s called the Writer monad. It’s probably not clear what the generic parts of the pattern are yet, so let’s take another example.

One problem you’ve likely dealt with many times is deciding whether a function should accept a single item as input or a list of items. The distinction is usually a matter of inserting a for loop around the function body, and this is usually boilerplate. But it does have a significant impact on how you are allowed to compose these functions. For example, suppose you have a function whose job is to take one DOM node and return all its children as an array; its function signature says that it takes a single HTMLElement and returns an array of HTMLElements.


// children :: HTMLElement -> [HTMLElement]
var children = function(node) {
  var children = node.childNodes, ary = [];
  for (var i = 0, n = children.length; i < n; i++) {
    ary[i] = children[i];
  }
  return ary;
};

// e.g.
var heading = document.getElementsByTagName('h3')[0];
children(heading)
// -> [
//      "Translation from Haskell to JavaScript...",
//      <span class=​"edit">​…​</span>​
//    ]

Now suppose I want to find the grandchildren of the heading, that is the children of the children of the heading. Intuitively, this seems like a good definition:

var grandchildren = compose(children, children)

But children does not have symmetric input and output types, so we cannot compose it like this. If we were to write grandchildren by hand, it might look like this:

// grandchildren :: HTMLElement -> [HTMLElement]
var grandchildren = function(node) {
  var output = [], childs = children(node);
  for (var i = 0, n = childs.length; i < n; i++) {
    output = output.concat(children(childs[i]));
  }
  return output;
};

We simply find all the children of all the children of the input node, and concatenate the resulting lists to produce one flat list of all the grandchildren. But this is not a convenient way to write it, and in fact contains a lot of boiler plate that results from the fact we’re working with lists, not from the problem we’re trying to solve. We’d rather just be able to compose two list-handling functions and be done with it.

Thinking back to our previous example, we need to take two steps to fix this: provide a bind function to turn children into composable form, and write a unit function to turn the initial input – the heading – into an acceptable type.

The core of the problem here is that our function accepts one HTMLElement and returns a list of them, therefore our conversions should be concerned with turning one item into a list of items and vice versa. The fact that the items are HTMLElements is not important, and in Haskell when the concrete type of something may very we use single letters to take their place. unit take an item and returns a list containing that item, and bind takes a ‘one-to-many’ function and returns a ‘many-to-many’ function.

// unit :: a -> [a]
var unit = function(x) { return [x] };

// bind :: (a -> [a]) -> ([a] -> [a])
var bind = function(f) {
  return function(list) {
    var output = [];
    for (var i = 0, n = list.length; i < n; i++) {
      output = output.concat(f(list[i]));
    }
    return output;
  };
};

We can now compose children as desired:

var div = document.getElementsByTagName('div')[0];
var grandchildren = compose(bind(children), bind(children));

grandchildren(unit(div))
// -> [<h1>…</h1>, <p>…</p>, ...]

We’ve just implemented what in Haskell is called the List monad, which lets you compose functions that map a single item to a list of items.

So what is a monad? Well, it’s a design pattern. It says that whenever you have a class of functions that accept one type of thing and return another type of thing, there are two functions that can be applied across this class to make them composable:

  • There is a bind function that transforms any function so that accepts the same type as it returns, making it composable
  • There is a unit function that wraps a value in the type accepted by the composable functions.

I should stress that this is very hand-waving imprecise definition that ignores the mathematical foundations of monads, which I don’t pretend to understand. But to someone doing the sort of programming I do, it’s a very useful design pattern to be aware of because it helps you spot accidental complexity: code that isn’t dealing directly with the problem at hand, but which is dealing with glueing data types together. Being able to spot and extract such boilerplate can radically improve the clarity of your code.