Let’s Make a Monad

We’ll make a Monad out of you yet

Specifically, let’s make Javascript’s native Array into a Monad! This is going to be easy, since Arrays are most of the way there already!

What’s a Monad? Well, one list of qualification is that it’s just a “pointed Functor that can flatten.” Let’s move right into seeing if Array qualifies so we can pick that apart piece by piece.

To start with, Arrays are definitely already Functors: they have a .map() method that conforms to the Functor laws, and that’s all we need to worry about at the moment.

Is Array “pointed?” Sorta. To say something is “pointed” is simple enough: it just means that there’s a method to lift a value up into the wonderful world of Arrays. Putting values into an array is pretty dang easy: you can literally just write it out in literal form, right?

[9] There, I put a 9 into an Array! Done.

…well that’s not quite what we mean: we need a functional way of doing that: a value-wrapping function that’s specific to Arrays. This sort of function might work: x=>[x].

Because with that, we can do things like: compose(xs=>[0,…xs], x=>[x]);

That is, if we have a value to start with, but want to use a function that expects an array, we can make sure to “upgrade” any value into an Array: the x => [x] operation will simply put the value into an array so that the next step, xs=>[0,…xs], has an Array to work with, as it expects:

compose(xs=>[0,…xs], x=>[x])(5) ;//-> [0,5]

You can see why having a pointed interface would come in handy when you’re piping together functions that expect different types, right?

Well, with ES2015, we even have a native version of “pointed” for Arrays (sort of). It’s called Array.of. As long as we only give it a single value, it should suffice for our purposes: Array.of(6) → [6]. Nice.

So far we didn’t have to do any actual work. But Arrays actually are missing the final bit: a Functor-ish way to “flatten.” As long as we don’t give a hoot about the dangers of extending native prototypes, that’s pretty easy to implement:

You should give a hoot about extending native prototypes though, because it’s a tricky, potentially dangerous thing to do in an actual production application. This is an unnecessary complication for understanding things at the moment though.

.flatten() will take an Array of Arrays and unnest it a single level, all thanks to both ES2015's neato spread operator and the almost magical behavior of Array.prototype.concat(). Are we a monad now?

Well, how would we know? We’d know because Array would obey the Monad Laws of course! No worries if you’re not familiar with them yet: we don’t need to understand them if all we want to do is to see if our modified Array type passes. Here’s a little test suite I cooked up… but for now please just skim over it, ignore the comments, and get right to the punchline at the end:

The punchline? This little set of tests repeatedly calls a method, .chain, that you and I should both be pretty sure that Arrays do not have. So, just having a .flatten() method (sometimes called .join() ) isn’t quite what we meant by “can flatten.” Flattening here isn’t just a smooshing down of an Array: it’s an operation that applies a specific function to each of the value(s) inside the Array, like .map(). In fact, it basically IS just a .map() plus a smoosh:

Some libraries even call this sort of operation .flatMap() (why not call it .mapFlat() instead, since that’s the order things happen? I dunno). As it happens, both Array.flatten and Array.flatMap are in talks to become an official part of Javascript.

Take my advice though: don’t just think of .chain as a convenient shorthand for .map().flatten(). In some ways it’s even more fundamental than .map, if you can believe it. That’s because once we define a legitimate .chain operation for some Monadic Type (as well as a pointed method), we can always easily and reliably derive a .map implementation from them. By first creating a version of Array.prototype.chain() from scratch without using either .map() or .flatten() I can even give you an example; I call it… map2:

Do not actually attempt to create .map2, it works exactly like .map, and we already HAVE .map

In any case, I’m sticking with .chain name largely because one of the reigning specs for this sort of thing does so. But also because, as we’ll see, the name fits.

It’s important to get a sense for why .chain only un-nests one level and one level exactly. Mapping normally involves a function that turns some value a into some new value b: a → b

But if you think about it, there are lots of functions out there that necessarily take a value and instead return container type like Array with the value inside. Array.of is a simple one we’ve already encountered: a → [a]. And if you’ve worked with ES6 Promises, you’ve probably created a lot of functions with this sort of type-signature: a → Promise[b] (e.g. a function that takes an api url route as a string, and returns a promise for a json result) Same deal.

But think about what would happen if we passed a function with that sort of type-signature, i.e. a → F[b], into just F.map() (F is just a generic container type which you can think of as an Array with just one item). Well, we’d end up with this:

Functor F :: F[a] → (a → F[b]) → F[F[b]]

So that’s annoying. But by automatically removing just the one outer-layer, we can instead achieve a new type signature of:

Monad M :: M[a] → (a → M[b]) → M[b]

Which is to say that now, even if we have a function that takes a value and returns a new Monad, we can still use it as a way to transform one Monad (with a value inside) seamlessly into another (same type, different value inside).

That might sound like a really obscure case, but think about what it means: even though the type of the inputs and outputs of a function like a → M[b] are necessarily different (i.e. not symmetrical), the inputs and outputs of a complete .chain(a → M[b]) operation… are the same. Which means… that these operations can now all cleanly compose again, the output of one piped right into the input of the next without any additional mental gymnastics.

Ok, that’s all hopefully suggestive and intriguing, but why would you ever want to .chain() Arrays, specifically? It’s the whole tautological purpose of what we’re up to here, of course: adding that capability to Arrays makes them legitimate Monad. (Array will now pass all those tests. You can go up and skim over them again now. Or check them out in a live REPL.)

But it’s not a very good answer, especially since I never really explained what a Monad was (and if you already know, odds are you didn’t bother reading this far). So again, why would you want to define .chain() and make native Arrays Monadic?

I will grant that, relative to other Monads, native javascript Arrays are not necessarily super interesting. We already take most of their functionality for granted, for one thing. And they don’t encapsulate any interesting additional behaviors like laziness, immutability, distinct subtypes, etc. But they do have the sort of flexibility you’d expect from Monads in general, some of which we’ll soon see in practice. And while the first Monad many tutorials introduce is something like Identity, Array-as-Monad at least does have some more obviously interesting use cases right out of gate (which the Identity type, mostly, does not).

One quick thing we can do quite easily now is intersperse values into an array without any sort of imperative loop:

[1,2,3,4].chain(x=>[x,0]).slice(0,-1);//-> [1, 0, 2, 0, 3, 0, 4]

Right? Normally, we can only work on and return a single result as we iterate over an Array, which makes “interspersing” things literally (and lawfully) impossible with just .map() alone. But let’s take that example up a notch. Say that we have some values in an Array and a function that returns three different permutations of each value. Just using .map() is going to return an array of arrays:

[1,2,3].map(x=>[x+1, x+2, x+3]);//-> [Array[3], Array[3], Array[3]]

…but we really want, as in a lot of common use cases, is a complete, shallow list of all the possible permutations for all the values. Again, .chain will do exactly that for us:

[1,2,3].chain(x=>[x+1, x+2, x+3]);//-> [2, 3, 4, 3, 4, 5, 4, 5, 6]

Because Arrays are now Monadic, there’s actually another, even neater way to represent this. Let’s start by treating each of the mutations as functions in their own right, and then stick THEM into an Array.

Array.of(x=>x+1, x=>x+2);//-> [function, function]

In some ways that’s even more intelligible, because now you can dynamically create/modify this collection of operations instead of having them all imperatively baked into a callback. Plus, we often find ourselves in a place where we know what computations we want to run long before we know what dataset(s) we will want to apply them to. So this is a pretty worthwhile pattern.

But now what? To actually use those functions, we’d need a way to pipe some array of values (which will become the arguments) into each function so that they can return a complete and comprehensive Array of the results. Well, as it happens, once we’ve defined Array as a Monad and have a .chain method, we can very easily derive another method: .ap:

a.map(x=>f(x)) could have just been written as a.map(f) but doing it the more verbose way protects f against any extra arguments that a particular version of map might pass other than just x, the value.

.ap, short for Applicative/Apply (but not exactly the same thing as Function.prototype.apply), allows us to take the value(s) in our Array Monad (values that happen to be functions) and, by mapping over a second Array that we’ve passed in to this new .ap method, run each function with each value in that second Array.

That means that we can just use the .ap interface we’ve created on any target Array and get a complete result (2 functions x 3 values = 6 results):

Array.of(x=>x+1, x=>x+2).ap([1,2,3]);//-> [2, 3, 4, 3, 4, 5]

Use cases for that?

Imagine a statistical plot where a list of base points needs to be represented on a graph but with several variations on the data that each represent basic possible transformations.

var curveOne = x=> [x, (x+1)*(x+2)];
var curveTwo = x=> [x, (x+3)];

[curveOne, curveTwo].ap([1,2,3,4,5]);

Note that in this case, we WANTED an Array of Arrays as output: those will be x,y points on the graph, after all. Which is why it’s important that .chain/.ap only unnests things by a single level (the one otherwise unintentional level) instead of flattening everything recursively.

For another twist, imagine a simple evolutionary simulation: you have a list of creatures, defined as objects with properties, representing a generation (we’ll stick with just numbers just to keep things clearer). You want to produce a new generation of creatures (i.e. a new list) based on several different possible mutations applied to each of the existing creatures. The applicative functor pattern is ideal for those sorts of cases because it allows you to easily marry multiple mutations with multiple targets. No additional looping or flattening code necessary.

That’s a really simple example of course, but it’s when things start to get complex that having a simple, flexible interface matters. Let’s say that our mutation functions all take more than one input, because hey, sexual recombination is a party. Can the applicative interface for Arrays handle that? Sure. As long as our functions are curried (i.e. won’t execute until they receive both of their arguments):

var mOne = curry((x,y) => x - y);
var mTwo = curry((x,y) => x + y);
var mThree = curry((x,y) => x * y);

Now we’re going to run two sets of beasties through all the possible permutations by just applying the first array of beasties and then applying the second array of beastie mates:

Array.of(mOne, mTwo, mThree).ap([1,2,3]).ap([10,11,12]);
//-> [-9, -10, -11, -8, -9, -10, -7, -8, -9, 11, 12, 13, 12, 13, 14, 13, 14, 15, 10, 11, 12, 20, 22, 24, 30, 33, 36]

That’s every beastie from the first array is matched with every beastie from the second array passed through every permutation we originally listed (itself just an array). The result is 27 new beasties (3 x 3 x 3). Under the hood, we just have our 3 curried functions in an Array. They each get one of their arguments applied in each of the 3 values from the first Array, and then each of those gets their second argument applied in from each value of the second Array. Thus complete, they return a result: a flattened Array.

This is a very flexible and intelligible representation of something that could very easily make your head hurt if you tried to write it out imperatively with loops and loops in loops (if you happen to intuit that these particular operations could also be achieved using transducers, gold star). It’s the sort of daunting “too mathy!” problem you might normally try to avoid because of all the potential head-hurtyness, but here managed neatly and easily. A well-constructed type can take care of all of the tricky bits for you.

Anyhow, that’s the core Applicative method, .ap() used to great effect with Arrays (allowing us to sort of reverse the operations we’d normally do with .chain()). How about some more use cases for .chain() directly?

James Colgan outlined a great one that we’ve all come across: working with DOM nodes. It’s easy, for instance, to write a function that takes a single DOMnode (a node object) and then finds all of its children (an Array of node objects):

var childrenOf = DOMnode => Array.from(DOMnode.childNodes);

But what does that give us? A function that takes a single item and returns an Array. And what’s the problem with that? Functions that don’t have the same types of inputs and outputs can’t really be glued together end-to-end, making them a lot less flexible and composable in practice. But if we’re looking for a list of all the grandchildren of some element (i.e. the children of the children), then composition is exactly what we want: we basically want to apply this function twice. How do we make that happen?

Let’s first make a convenience version of document.getElementsByTagName (which always returns an Array even if it finds one or no nodes):

var $byTag = tag => Array.from(document.getElementsByTagName(tag));

With that, we have a function that returns an Array of DOMnodes (a real Array too: thanks Array.from!), which means that we can just .chain() on our asymmetric childNode finding function, childrenOf. And we can even do it twice, as advertised:

$byTag(‘body’).chain( childrenOf ).chain( childrenOf );

That returns all the children of the children of the body tag! Easy peasy. How about if we wanted to define a named function that does all this, instead of explicitly chaining? Let’s create a nice “pointfree” helper that takes a function and a Monad and then delegates to the .chain method of whatever Monad we happen to pass in (making no assumptions):

var chain = curry( (f, xs) => xs.chain(f) );

Now we can write:

var grandchildrenOf = compose( chain(childrenOf), chain(childrenOf) );

And then use it like:

grandchildrenOf( $byTag(‘body’) );//-> [Boatload,O’,DOMnodes]

Monad in, Monad out. Which is to say: Arrays all the way through as we compute our (Array) result. And to do that, we’ve basically taken the simple, but asymmetric, childrenOf and made it so that the operation, in-toto, is symmetric. We can .chain() on as many childrenOf functions as we want to get the depth we desire and it all works: without having to over-complicate childrenOf.

Between .map(), .ap(),.chain() we now have a more complete sort of honeybadger-ish toolkit. We can perform sensible computations on the values inside our Monadic containers (Arrays here, but they’re just the tip of the iceberg) regardless of whether those computations are the sort that return single values or Arrays themselves. Freedom!

Libraries like jQuery handle some of this sort of magic under the hood (even though phrases like “jQuery is a Monad” are generally more confusing than enlightening). But with jQuery falling out of favor, it’s worth knowing how the magic works more directly.

I know that we still haven’t really talked about what Monads really are: which is to say, the full truth of the generalized pattern. And I don’t plan to at the moment: there are a million other great tutorials out there. Honestly though, I think it’s worthwhile to first have a good, vague intuition about how common and useful a pattern this is before anyone tries to get you too apprehensive about how deep it is.

That’s because there are Monadic patterns out there that you’re already comfortable using and intuiting about. We just saw how minor a change it takes to make Array a Monad, and why that can be useful.

I’d also argue that ES2015 Promises are Monads as well, right out of the box.

Sure: they do weirdly boil .map() and .flatMap()/.chain() into the same overly-smart operation: .then() That can be a little confusing in theory, and violates some of the “standardized behavior = generalizable operations” spirit of functional programming, but it mostly works out very naturally in practice.

Their pointed function is found at Promise.resolve instead of Promise.of, but that also should make sense: you’re lifting a known value up into a Promise, and since it’s just a value, not an error, it makes sense that it’s in the resolved state. (Why would you lift a simple value into a Promise in the first place? Well…) If you’d like, you could always just alias it: Promise.of = x=> Promise.resolve(x)

It’s also worth recognizing that Promises are not, strictly speaking, pure (when you create one, its IO evaluation is immediate/eager rather than waiting to be called on, and most Promise-returning functions depend on some external state, like an api). But, for all those caveats, they do obey the basic Monadic laws all the same: http://goo.gl/tCQ3c4

And because they do that, then even if you don’t know what it means to say that they are Monads, you do already know several powerful somethings about how they behave.

You know what types of functions .then() can handle, for instance: unary functions that return either values (because it’s a Functor and can map) or new Promises directly (flatMapping). But you also know for dead sure that because Monads are inherently Applicatives, it’s possible to write an applicative interface for Promises using .then(). It’s even possible to imagine an interesting use case:

A function inside a Promise, instead of a value? I bet you never even thought that Promises could be used like that (Imagine a Promise that returned a normalized function interface for one of two possible APIs, determined at runtime…)! But is it really better than doing this instead?

Maybe, maybe not. Both work. It all depends on how and when and what pieces and in what part of your application all this stuff needs to happen.

But here’s another important realization: Promise.all and our original Array.ap method actually share some pretty important connections. I, like many ES6 enthusiasts, may have taken something like Promise.all for granted: some mysterious function that merges promises (a native replace for jQuery’s $.when). But let’s think through it a bit more closely.

What is the basic signature of Promise.all? It takes an Array and returns a Promise, sure, but more specifically: it takes an Array of Promises, and returns a Promise… of Arrays. So it’s a complex type wrapped around another complex type, but then with that wrapping flipped inside out! How is that accomplished? With Promise.all, it’s a sort of black box, and very specific to Arrays and Promises.

But as it turns out, this is a more general transformation: sequence. We can explore it more later, but it’s an example of the sort of generalized gymnastics we’re opening up for ourselves when we implement these types.

In the end, these patterns we’ve been talking about are all in service of giving your declarative code exactly the degrees of flexibility you might need to express exactly what you want.

Flexibility by itself can be a nightmare (too many ways to do the same thing), but the flexibility here is constrained by a very specific set of well known laws and properties. That’s why it’s cool. 👲

One clap, two clap, three clap, forty?

By clapping more or less, you can signal to us which stories really stand out.