How I understood monads, part 1/2: sleepless and self-loathing in Seattle

For some time now, I had been noticing some interest for monads, mostly in the form of unintelligible (to me) blog posts and comments saying “oh, yeah, that’s a monad” about random stuff as if it were absolutely obvious and if I didn’t know what they were talking about, I was probably an uneducated idiot, ignorant about the simplest and most fundamental concepts of functional programming. Fair enough, I am pretty much exactly that.

Being the kind of guy who can spend eight years in college just to understand a few interesting concepts about the universe, I had to check it out and try to understand monads so that I too can say “oh, yeah, that’s a monad”.

Man, was I hit hard in the face with the limitations of my own abstract thinking abilities. All the articles I could find about the subject seemed to be vaguely understandable at first but very quickly overloaded the very few concept slots I have available in my brain. They also seemed to be consistently using arcane notation that I was entirely unfamiliar with.

It finally all clicked together one Friday afternoon during the team’s beer symposium when Louis was patient enough to break it down for me in a language I could understand (C#). I don’t know if being intoxicated helped. Feel free to read this with or without a drink in hand.

So here it is in a nutshell: a monad allows you to manipulate stuff in interesting ways. Oh, OK, you might say. Yeah. Exactly.

Let’s start with a trivial case:

public static class Trivial {
    public static TResult Execute<T, TResult>(
        this T argument,
        Func<T, TResult> operation) {

        return operation(argument);
    }
}

This is not a monad. I removed most concepts here to start with something very simple. There is only one concept here: the idea of executing an operation on an object. This is of course trivial and it would actually be simpler to just apply that operation directly on the object. But please bear with me, this is our first baby step. Here’s how you use that thing:

"some string"
  .Execute(s => s + " processed by trivial proto-monad.")
  .Execute(s => s + " And it's chainable!");

What we’re doing here is analogous to having an assembly chain in a factory: you can feed it raw material (the string here) and a number of machines that each implement a step in the manufacturing process and you can start building stuff. The Trivial class here represents the empty assembly chain, the conveyor belt if you will, but it doesn’t care what kind of raw material gets in, what gets out or what each machine is doing. It is pure process.

A real monad will need a couple of additional concepts. Let’s say the conveyor belt needs the material to be processed to be contained in standardized boxes, just so that it can safely and efficiently be transported from machine to machine or so that tracking information can be attached to it.

Each machine knows how to treat raw material or partly processed material, but it doesn’t know how to treat the boxes so the conveyor belt will have to extract the material from the box before feeding it into each machine, and it will have to box it back afterwards.

This conveyor belt with boxes is essentially what a monad is. It has one method to box stuff, one to extract stuff from its box and one to feed stuff into a machine.

So let’s reformulate the previous example but this time with the boxes, which will do nothing for the moment except containing stuff.

public class Identity<T> {
    public Identity(T value) {
        Value = value;
    }

    public T Value { get; private set;}
    
    public static Identity<T> Unit(T value) {
        return new Identity<T>(value);
    }

    public static Identity<U> Bind<U>(
        Identity<T> argument,
        Func<T, Identity<U>> operation) {

        return operation(argument.Value);
    }
}

Now this is a true to the definition Monad, including the weird naming of the methods. It is the simplest monad, called the identity monad and of course it does nothing useful. Here’s how you use it:

Identity<string>.Bind(
    Identity<string>.Unit("some string"),
    s => Identity<string>.Unit(
        s + " was processed by identity monad.")).Value

That of course is seriously ugly. Note that the operation is responsible for re-boxing its result. That is a part of strict monads that I don’t quite get and I’ll take the liberty to lift that strange constraint in the next examples.

To make this more readable and easier to use, let’s build a few extension methods:

public static class IdentityExtensions {
    public static Identity<T> ToIdentity<T>(this T value) {
        return new Identity<T>(value);
    }

    public static Identity<U> Bind<T, U>(
        this Identity<T> argument,
        Func<T, U> operation) {

        return operation(argument.Value).ToIdentity();
    }
}

With those, we can rewrite our code as follows:

"some string".ToIdentity()
    .Bind(s => s + " was processed by monad extensions.")
    .Bind(s => s + " And it's chainable...")
    .Value;

This is considerably simpler but still retains the qualities of a monad. But it is still pointless.

Let’s look at a more useful example, the state monad, which is basically a monad where the boxes have a label. It’s useful to perform operations on arbitrary objects that have been enriched with an attached state object.

public class Stateful<TValue, TState> {
    public Stateful(TValue value, TState state) {
        Value = value;
        State = state;
    }

    public TValue Value { get; private set; }

    public TState State { get; set; }
}

public static class StateExtensions {
    public static Stateful<TValue, TState>
        ToStateful<TValue, TState>(
            this TValue value,
            TState state) {

        return new Stateful<TValue, TState>(value, state);
    }

    public static Stateful<TResult, TState>
        Execute<TValue, TState, TResult>(
            this Stateful<TValue, TState> argument,
            Func<TValue, TResult> operation) {

        return operation(argument.Value)
            .ToStateful(argument.State);
    }
}

You can get a stateful version of any object by calling the ToStateful extension method, passing the state object in. You can then execute ordinary operations on the values while retaining the state:

var statefulInt = 3.ToStateful("This is the state");
var processedStatefulInt = statefulInt
    .Execute(i => ++i)
    .Execute(i => i * 10)
    .Execute(i => i + 2);
Console.WriteLine("Value: {0}; state: {1}",
    processedStatefulInt.Value, processedStatefulInt.State);

This monad differs from the identity by enriching the boxes. There is another way to give value to the monad, which is to enrich the processing. An example of that is the writer monad, which can be typically used to log the operations that are being performed by the monad. Of course, the richest monads enrich both the boxes and the processing.

That’s all for today. I hope with this you won’t have to go through the same process that I did to understand monads and that you haven’t gone into concept overload like I did.

Next time, we’ll examine some examples that you already know but we will shine the monadic light, hopefully illuminating them in a whole new way. Realizing that this pattern is actually in many places but mostly unnoticed is what will enable the truly casual “oh, yes, that’s a monad” comments.
Part 2/2 of this series can be found here:
http://weblogs.asp.net/bleroy/archive/2010/06/29/how-i-understood-monads-part-2-2-have-we-met-before.aspx

Here’s the code for this article:
http://weblogs.asp.net/blogs/bleroy/Samples/Monads.zip

The Wikipedia article on monads:
http://en.wikipedia.org/wiki/Monads_in_functional_programming

This article was invaluable for me in understanding how to express the canonical monads in C# (interesting Linq stuff in there):
http://blogs.msdn.com/b/wesdyer/archive/2008/01/11/the-marvels-of-monads.aspx