Rambling About Monads Part 1

I will attempt to describe monads usefully. I expect to fail. The attempt may be instructive.

Monads look something like this

M1 a >>= M2 b

It might read as “M1 applied to a binds to M2 applied to b”. M1, M2, a, and b are all data types. M1 and M2 are “monadic types” while a and b can be any type (including monadic). They can also be the same as one another, but I want to illustrate that they can be different. Monadic types are special because monads can operate on them. More on that later.

The >>= portion is called “bind” and I’m using the syntax from the Haskell language because it is one of the only languages I know of to treat monads as first class citizens, and it has an operator specifically for them.

In this article I will attempt to lay out how the above abstract definition applies to a real-world example. I will be using pseudocode that looks like either C# or Java, which may seem ironic, but they have static typing which makes it easier to illustrate my point in certain ways. Contrast with JavaScript which wishes types didn’t exist at all. I simply don’t know Haskell or other purely functional languages well enough to tutorial with them, and neither do you (probably).

My “Real-World” Example

I have an array of numbers, and I want to count all the ones greater than 5. Here it is procedurally:

int countGreaterThanFive(int[] values) {
    int count = 0;
    for (i=0; i<values.length; i++) {
        if (values[i] > 5) count++;
    }

    return count;
}

Why Would You Monad This?

I suggest that it is very common for a programmer to wish to iterate over an array and perform some operation on each value. I also suggest that in most cases, it is not necessary to consider multiple elements in an array at the same time. It is not about bending over backwards to solve this problem using monads. It is about seeing the bigger picture and generalizing the problem, solving it, and then applying that solution to solve this toy problem.

Alright, Then How Do You Monad This?

Let’s work backwards a little bit. Here is the final solution:

int countGreaterThanFive(Collection<int> values) {
    return monadValues
        .map(x -> x > 5 ? 1 : 0)
        .reduce(0, (x, acc) -> x + acc);
}

You may have heard of map-reduce. It’s a common big data analytics algorithm used by systems like Hadoop. It is just a combination of two monads deployed at scale and in parallel, but you can perform your own map-reduce in Java or C# or JavaScript.

You Dirty Cheater

Yes, I am, but I think it’s easier to start with something you’re familar with.

Translating Definition To Implementation

map and reduce themselves are not monads. The whole map(x -> x > 5 ? 1 : 0) line is the monad. Let’s look again at the definition of a monad and focus on how it turns into that map(... line.

M1 a >>= M2 b

The map function takes as its only parameter another function. It runs that function on every value in the Collection and returns a brand new Collection containing the output values. Here’s what the implementation might look like:

class Collection<T> {
    // ... other methods

    Collection<V> map(Function<T, V> f) {
        var result = new Collection<V>();

        foreach (T value in _internalCollection) {
            result.add(f(value));
        }

        return result;
    }
}

Collection is a monadic type, because it generically defines semantics around other types (in most statically typed languages these are called generics), and because our map function operates on it. So let’s replace the M1 and M2 in our definition with Collection for both.

Collection<a> >>= Collection<b>

Now, the implementation of map does not say that the input or output have to be any specific type, but in our function, we’re operating on int values. The anonymous function x -> x > 5 ? 1 : 0 is being run against members of the values argument, which is of type Collection<int>, so x here is an int. The output is either 1 or 0, which in absence of casting are assumed to be integers. So now we have:

Collection<int> >>= Collection<int>

So what about >>=? Well, I’ve already talked about it a little. Remember, it’s called “bind”, and it’s the combination of two things:

In this case, it’s map plus the function x -> x > 5 ? 1 : 0. You need both of those for a successful bind. So let’s do a little more replacement, and…

Collection<int> Collection<int>::map(Function<int, int>)

I had to move some things around for this to become proper OO-style syntax. This means that if you fix your generic types to be int, this is the actual signature of the map method. And that is the definition of our map monad.

Which Part Of This Is The Monad?

All of it, but you can refer to it by the name of the function that takes your function, so we’re calling this the map monad.

Chaining Monads

One important property of monads is that, because their input and output are both monadic types (albeit, possibly different ones), you can chain monads together. That’s why in the example above, I can write map().reduce(). reduce is another monadic function, but it cheats a little bit.

Cheating At Monads

Here’s my implementation of reduce:

class Collection<T> {
    // other methods

    V reduce(V initial, Function<T, V, V> f) {
        // I'm using C#'s Function object. The last generic type is always the return type. The others are arguments.

        V accumulator = initial;

        foreach (T value in _internalCollection) {
            accumulator = f(value, accumulator);
        }

        return accumulator;
    }
}

This does some very useful work. It allows us to compress a Collection of items down to a singular value. But, if you attempt to perform the same exercise we did with map and the definition of a monad, it doesn’t quite work.

Well, there’s no getting around point (1) without introducing some other concepts and making the implementation uglier. Suffice to say that technically the initial argument there is not part of the monad.

For point (2), there is a way around this. There is a special monad called the “identity” monad. It wraps any type and it always has a value. This is more useful conceptually than practically, so we just omit it, but we could write the return from reduce like this:

        return new Identity<V>(accumulator);

But that just clutters the code up for the sake of being 100% faithful to monads.

Notice that in our specific case, this terminates the monadic chain. Generally, you won’t be able to perform monadic operations on lowly int type variables. However, reduce will return whatever type your function does. If you reduce down to a monadic type, then you can continue the chain.

Epilogue

I hope that was useful to you. I may have oversimplified some parts of this and I expect could be mistaken about some of this stuff, but I reckon at least 50% of this is accurate.

Next: how do you learn to write your own monads?