Functional programming is a bit like writing regular expressions, in that the effort-expended-per-character is really high. It’s always annoyed me how Enlightened Functional Programmers online love to use bizarre names like “ap” and “<$>” for their functions – it makes me wonder if they’re using some experimental compiler that charges them a few cents per character.

The reason for this seems to be that it’s really hard to name things that are as general as monads, applicatives, and so on. When Lists, Optional types and Future values are all monads, what do you call a method which works for all of them? liftA2 might be a horrible function name, but I can’t really think of a better one.

Anyway, I’ve tried to avoid being too much of a functional programming extremist in this code. Primarily, that’s because I’m not smart enough to be one. But also, I didn’t want the code to be absolutely impenetrable to people who haven’t used monads before; I tried to make the API as reasonable as possible.

I’ve written a decent introductory explanation of monads at the bottom of this post: you’ll spot it by the radioactive signs. I think it gives a good overview of monads for people whose brains work like mine.

Do Notation: Hacking Generators

(Fair warning: if you're not an FP nerd, this might be intolerably jargon-y. Feel free to skip to the Monads explanation first and come back here.)

Here’s a sample of the sort of code you can write with this do-notation in Python:

def product2(monad_a, monad_b):
    x = yield monad_a
    y = yield monad_b
    return (x, y)

These monads can be anything: lists, optionals, futures, whatever. The only restriction is that you can’t interleave side-effects with the “yield” calls – they’ll be run more times than you expect. Side effects and other calculations are fine as long as they all go after the last yield keyword.

Why is this? Well, it stems from the fact that you can’t copy running generators in Python.

The yield keyword is used here because it lets functions behave like coroutines. That is, you can send values into them and get values back out again. Their execution is driven by an outside agent calling next(g) or g.send(…).

Compilers (and people) understand do-notation as nested bind calls, where the function passed in to bind is, in some sense, a callback to the rest of the do-block. But where that’s hard to do in Python is where Lists are involved – calling bind will mean that the rest of the do-block needs to be run more than once.

In imperative, non-compiled-land, this means we need to somehow duplicate the state of our coroutine. Unfortunately, CPython doesn’t provide a way of doing this natively; PyPy used to, but now seems to exhibit the same error as Python.

To do this manually (and with the caveat that side-effects can’t be interleaved with yields), I wrote a function called run which recursively calls bind with a partial application of the unwrapped values we’ve got so far inside the do-block.

Here’s how it looks:

Note that I’ve defined __rshift__ on the monad class as just syntactic sugar for the .bind() method. The key here is the advancing generator, building up of values_so_far in the recursive call, and catching the final StopIteration when the generator is exhausted – that is, when the function is complete.

The fact that this is defined in terms of a recursive call via bind() means that it works for anything with a bind method. So lists and optionals work just how you’d expect them to. I’m planning to write some more interesting monads like Writer and Future, too, to show off just how flexible this notation is.

If this has all been complete gobbledegook, please see my intro to monads below: it’s much more readable.

☢️ Monads Explanation ☢️

I think the main benefit of monads is that you can write a lot of really general code which sequences them together, without needing to know what they actually /are/ under the hood.

Especially for object-oriented people, it’s useful to think of a monad like an interface. It’s got to have two methods in particular: point and bind. These are totally, ridiculously obscure names. And I think that’s why so much FP is hard to get into; because generally programmers are used to thinking about what methods /do/, instead of what /types/ they have.

(Note: I’m going to keep calling them “methods”, even though it’s not 100% correct – who cares.)

The “point” method lets you create a new instance of a monad. For the List monad, it transforms x into [x]. For the Optional monad, it transforms x into Some(x). For the Future monad, it transforms x into a Future(x). People tend to be pretty comfortable with the point method, because it’s basically a constructor. It “wraps” a type into the List, Option, Future, or whatever other thing you’re dealing with.

The “bind” method is slightly trickier. It takes two parameters: firstly the monad (list, option, future etc.) itself; and secondly, a function which transforms a regular value into the same monad we’re using.

Here’s the type signature of bind, for the List monad:

bind :: List x -> (x -> List y) -> List y

And here’s the type signature of bind, for the Option monad:

bind :: Option x -> (x -> Option y) -> Option y

You can make this more general-purpose by swapping “Option” or “List” here for whatever monad you’re currently thinking about.

bind :: SomeMonad x -> (x -> SomeMonad y) -> SomeMonad y

This seems a bit weird, especially for Lists. Why would a function take a single value and return a list? Well, fair point. A lot of the time, you don’t really need a monad, and you could do with something a bit weaker – something like a Functor, which has a map method but no bind.

(Note: there’s actually a whole /hierarchy/ of types. If you’re thinking “hang on, you can map over lists! Is List really just a Functor?”, then you’re right – a Monad is a /subtype/ of Functor. That means anything you can do with a Functor – in this case, the “map” operation – you can do with a Monad, too.)

Where monads get useful, though – and how they’re often explained – is the idea of /sequencing computations/. I’m going to use JavaScript Promises as an example, but you should know that for pedantic technical reasons involving objects with a ‘then’ key, Promises aren’t actually Monads. But they’re like 98% of the way there, and they’re pretty ubiquitous.

Let’s look at some example Promise code in JavaScript.

  .then(data => {
    return decode(data)
  .then(decodedData => {
    return process(data)

And let’s assume that these three things return Promises:

  • fetch(url)
  • decode(data)
  • process(data)

Now let’s think about the types in the code we’ve just seen. Specifically, what’s the type of the .then() method?

Well, let’s squint a bit, and say that because .then() is a /method/ – as in, it’s attached to the Promise object – then that Promise object can count as the first parameter to our function.

then :: Promise data -> …

(In JavaScript you have to squint a bit to believe this. But it’s a bit more explicit in Python, where to write a method you declare self as the first parameter.)

Now let’s see what the next parameter is. We’re passing an anonymous function which takes data as its first parameter: this isn’t a Promise, this is just a bit of data. But we return decode(data), which in our handy bullet-pointed-list above we’ve said above actually returns a Promise.

(Is decode(data) a real API? No. But there are plenty of browser APIs that accept data and return promises – take the method to convert fetch-data to an array buffer, for example. I just didn’t want to muddy the waters with implementation details. The important thing is the type of these functions, not what they actually do.)

So the value we’re passing into then is of this type:

<anonymous> :: data -> Promise decodedData

In other words, our anonymous function accepts some data and returns a Promise of some decoded data.

We’re passing this function to our .then method. Let’s look at how the type signature looks now:

then :: Promise data -> (data -> Promise decodedData) -> …

Now let’s try and fill in the blanks at the end. This is just a bit of JavaScript knowledge, but the point of .then is to let you chain promises together: what we end up with is a Promise of decodedData.

then :: Promise data -> (data -> Promise decodedData) -> Promise decodedData

So we’ve written out our type signature for the .then method. Why am I spending so much time and effort on this?

Well, let’s have another look at our bind type from earlier:

bind :: SomeMonad x -> (x -> SomeMonad y) -> SomeMonad y

See the similarity? Here we’re just renaming “x” to “data”, “y” to “decodedData”, and our monad to “Promise”.

(If you remember from earlier, to make Promise a monad, we also need a “point” to wrap any value into a Promise: Promise.resolve(x)  fulfills that requirement.)

The useful thing to take away here is that we’re able to string together chains of functions which accept plain data and return Promises. fetch, decode and process all let us do asynchronous computing without worrying about the results immediately, by giving us a Promise – a future result that we can slap a callback on.

This is what people mean when they say Monads let you sequence computations. A Promise is sort of like a “computation” on its value – it’ll resolve at some point in the future.

This is also what people mean when they say Monads are like a “computational context” for values. In the case of a List type, the “context” is that there’s more than one value, and we tend to do things to each value in the list. For an Optional type, the context is that the value might not be there, and we don’t try to call functions on values that aren’t there. If you want to write a monad, that context is your job as a programmer to write in the bind method, if you want to create a monad type.

There’s some rules about monads which I think are only useful to learn when you’re really invested in functional programming. They aren’t particularly intuitive and don’t really help you write general-purpose code. The idea of monads as the interface with “point” and “bind” is incredibly powerful, and lets you write genuinely abstract code. Worrying about homomorphisms at this point, I think, is more for the theory nerds – although there are some interesting implications for Promises.

Do Notation

This notation starts off being quite confusing, especially when people use the term “return” to mean subtly different things in different languages. But it’s a really smart idea.

Let’s say you have some variable which is of type Future x. As in, at some point in the future, you’ll have an x. And you have a similar variable of type Future y.

It’d be handy to sequence something to happen when both Futures are resolved. Ordinarily, we’d do that like this:

future_x.bind(x =>
  future_y.bind(y =>
    doSomething(x, y)

Inside the two nested functions, we have access to x and y as “real” values, and we can pass them to a function call, add them together, access properties on them, whatever we like. But the trick is that that inner function will only be called AFTER the futures have resolved.

However, it can get boring to have to write .bind a hundred times in a row. And we’ve only got so much horizontal space available. So people came up with a smart way of writing code which compiles to nested .bind calls:

do {
  x <- future_x
  y <- future_y
  doSomething(x, y)

It’s the same outcome, but suddenly it looks more like the synchronous code we’re used to writing!

Although JavaScript doesn’t have support for do-notation syntax generally, it has introduced one special-case form of do-notation for an incredibly popular monad(ish) type: Promises.

async () => {
  x = await promise_x
  y = await promise_y
  doSomething(x, y)

Although the comparison with JS promises and async/await is a useful one, it’s sometimes a bit limiting. For example, in functional languages like Scala, it’s possible to use do-notation with very different monads like the Option monad:

do {
  x <- maybeX
  y <- maybeY
  doSomething(x, y)

In this pseudocode, doSomething(x, y) will only be called if x and y are both Some values. It’s exactly the same syntax, for a very different effect.

Equally, here’s a way to print all the possible combinations of a two-digit bike lock:

do {
  a <- [0..9]
  b <- [0..9]
  print(a, b)

In this case, the values a,b,c and d will take on each subsequent value in each of their lists. So the printed results will be “0 0 0 0”, “0 0 0 1”, etc., all the way up to “9 9 9 9”.

Three completely different effects; all the same syntax. The common feature here is that we're leaning on the definition of bind for each type in turn: Promises (with .then() acting as our bind function); Optionals, and Lists.

In order to use this powerful compositional tool, programmers just need to implement two methods: point and bind. How bind works is largely up to them – so it's important to get right. However, when that's done, it can lead to powerful and abstract code which works for very diverse types.