Monads in C++

09 Sep 2013, 10:00 UTC

A monad is just a monoid in the category of endofunctors, what's the problem?

I've been struggling with the concept of monads for years. They are usually described using some hardcore functional language, with unfamiliar syntax. Or, they are described in abstract mathematical terms, with no obvious connection to reality. Most explanations seem to only make sense if you already know what a monad is. But today the penny finally dropped for me, so following the theory that "the best person to explain monads is someone who didn't understand them himself until this morning", I offer this explanation of monads, which (hopefully) any C++ programmer should be able to follow.

A Problem

In C++ you can write the following code:

printf("Hello ");
printf("World\n");

Hello World
_

You can't do this in a pure functional language. In such a language, every function has a single statement of the form return <expression>. There are no semicolons, and the expression format has no comma (sequencing) operator. Sure, you can do something like this ...

return print("Hello ") + print("World\n")

... assuming print returns something like "number of characters printed". But the compiler is free to evaluate the operands to + in any order. The exact order will be based on the compiler's optimization logic. You could easily end up with this on screen:

World
Hello _

How do we solve this? How do we sequence things in a language that has no sequencing primitives?

You Already Know The Solution, You Just Don't Know It Yet

Imagine an image processing library. You have a class like this:

class Image
{
public:
    Image(void * data, ImageFormat format, int width, int height);

    Image ApplyFilter(FilterFunction fn) const;
};

Now you can write things like this:

Image MakeBlackAndWhiteMaxContrastImage(void * data, ImageFormat format, int width, int height)
{
    return Image(data, format, width, height).ApplyFilter(IF_MakeBlackAndWhite).ApplyFilter(IF_MaximizeContrast);
}

In C++ we would consider this just syntactic sugar for creating filtered images. Lots of C++ libraries do things like this. It's obvious which order the filters get applied in, because each filter takes the output of the previous filter as an input. Of course the second filter must be run after the first filter.

But by doing this we have sequenced the operations. We know which order they are executed in. And we have never used the semicolon or the comma operator - we are in pure functional form.

Now you understand the basic operation of monads!

Towards Monadic Theory

So how do we make a "classical" monad? If you read the monad texts you'll find that a monad needs a "unit" operator and a "bind" operator. What the hell are these?

To explain, let's make a monad that does nothing. We'll restrict ourselves to thinking about integers only, to make the explanation easier (later we can use templates, because a monad is really more like a template than a single class, but for now we'll just look at a single class).

class IntMonad
{
public:
    IntMonad(int value) : m_value(value) { }

    typedef IntMonad (*IntMonadOperation)(int value);

    IntMonad Do(IntMonadOperation op) const { return op(m_value); }

private:
    int m_value;
};

In monad theory, the "unit" operator is the constructor IntMonad(int) and the "bind" operator is the Do operation. That's all there is to it. The "kind" of the monad is determined entirely by what the constructor(s) do, and by the code in the Do operation (and by the member variables, which kind of follow from those).

One thing to note is that since IntMonad has no "get" function, we have to unwrap m_value inside the Do function, which means the input to IntMonadOperation is an int and not an IntMonad. This guarantees to the called function: the data you are receiving actually is an int. The output of IntMonadOperation is an IntMonad, though, so we could store auxiliary information from the function in the monad, as well as (or instead of) the main return value. In this example, neither of these two facts is important, but they will be important for the IntMaybe monad we'll see later.

We can now define some functions as follows:

IntMonad IM_Make(int value) { return IntMonad(value); }
IntMonad IM_Increment(int value) { return IntMonad(value + 1); }
IntMonad IM_Square(int value) { return IntMonad(value * value); }
IntMonad IM_Print(int value) { printf("%d\n", value); return IntMonad(value); }

There are two interesting things to note here; neither is crucial to your understanding of this:

First, IM_Make is just the constructor, and can also be considered a "unit" operator (this is another reason for IntMonadOperation to take an int and return an IntMonad - so IM_Make can be an IntMonadOperation).

Second, the IntMonad constructor is called in every operation just after the return keyword. For this reason the constructor is also called the "return" operator in Haskell (the normal "return" operation in C++ is redundant in functional languages, since every function is of the C++ form return <expr>).

So let's do something with this class:

IntMonad(10).Do(IM_Increment).Do(IM_Print).Do(IM_Square).Do(IM_Print);

11
121
_

The prints occur in the order expected, and give the expected results, but all because of data dependencies, rather than because of sequencing operations in the core language.

But we've done nothing useful here - those data dependencies already existed for this example. We've not actually introduced anything new, because the simpler Square(Increment(10)) with Square and Increment implemented in the obvious way also has the Increment run before Square. It has to, because Square needs the result of Increment. But, by using a class with no data, we can implement a kind of "pure sequencing" that still works in this way and actually does introduce a new capability. That's the IO monad.

An IO Monad

The IO monad is even simpler than IntMonad:

class IO
{
public:
    IO() { }

    typedef IO (*IOOperation)();

    IO Do(IOOperation op) const { op(); return IO(); }
};

IO IO_PrintHello() { printf("Hello "); return IO(); }
IO IO_PrintWorld() { printf("World\n"); return IO(); }

return IO().Do(IO_PrintHello).Do(IO_PrintWorld)

Hello World
_

This is our original printf sequencing problem solved.

Note that the IO monad doesn't contain any state at all that does this sequencing. Descriptions of this monad often say the IO monad represents "the state of the whole world" - and it does represent that, it just doesn't contain it!

An interesting question is what happens when we "fork" a monad, as follows:

IO myIo = IO();
myIo.Do(IO_PrintHello).Do(IO_PrintWorld);
myIo.Do(IO_PrintHello).Do(IO_PrintWorld);

(Assume for now that the ; just means "do both these things" not "do these things in this order".)

You should be able to infer that the first "Hello" is printed before the first "World", and the second "Hello" is printed before the second "World", but the two "Hello World"s may be printed in any order relative to each other, and interleaved with each other. So we might get this on screen:

Hello Hello World
World
_

This is what can happen with multiple threads doing printf. So each expression using the IO monad is like a "thread", and execution between "threads" can happen in any order. On the other hand,

IO myIo = IO();
myIo = myIo.Do(IO_PrintHello).Do(IO_PrintWorld);
myIo.Do(IO_PrintHello).Do(IO_PrintWorld);

will always produce this:

Hello World
Hello World
_

Can you see why?

A Maybe Monad

I promised a Maybe monad. With the Maybe monad, each operation can either succeed or fail. If an operation fails, all later operations in the chain must be eliminated. The Maybe monad carries extra state to achieve this:

class IntMaybe
{
public:
    IntMaybe(int value) : m_value(value), m_valid(true) { }
    IntMaybe() : m_value(0), m_valid(false) { }

    typedef IntMaybe (*IntMaybeOperation)(int value);

    IntMaybe Do(IntMaybeOperation op) const
    {
        if (m_valid)
            return op(m_value);
        else
            return IntMaybe();
    }

private:
    int     m_value;
    bool    m_valid;
};

Now we can define operations that can either succeed or fail, for instance by overflowing an int:

IntMaybe IM_Square(int a) { return (abs(a) >= 0x8000) ? IntMaybe() : IntMaybe(a * a); }

return IntMaybe(0xC000).Do(IM_Square).Do(IM_Square)

You can see that the second call to IM_Square will never be executed, and that the result is IntMonad() (this is called "Nothing" in the Haskell Maybe monad; the other case is called "Just x").

Now we can see why m_value is unwrapped in "Do", rather than in each IntMaybeOperation - it avoids boilerplate in those operations, checking for the invalid case. We can also see why IntMaybeOperation returns an IntMaybe rather than an int - we need the option to return an invalid object, instead of a wrapped int object.

What about adding two numbers in this system? Well, in Haskell this is fairly simple to do, using first-class functions. Replicating the same thing in C++ is not so easy. But we can implement a simple solution by adding the following to IntMaybe:

typedef IntMaybe (*IntMaybeOperation2)(int value1, int value2);

IntMaybe Do2(IntMaybeOperation2 op, IntMaybe p2) const
{
    if (!m_valid || !p2.m_valid)
        return IntMaybe();
    return op2(m_value, p2.m_value);
}

IntMaybe Add(int a, int b) { return OverflowOnAdd(a,b) ? IntMaybe() : IntMaybe(a + b); }

An exercise for the reader is to do this using just the Do operator, and pretending that C++ has first-class functions :)

Monad Legaleze

In monad theory, monads have three "laws", and the laws can be explained using any of our example classes, for instance the IntMonad class. The laws merely say that:

1. IntMonad(a).Do(f) has to have the same effect as just f(a).
2. im.Do(IM_Make) has to have the same effect as just im.
3. im.Do(f).Do(g) has to have the same effect as im.Do(fg) where fg is defined as follows:

IntMonad fg(int value)
{
    return f(value).Do(g);
}

The reason for these laws are fairly obvious - you could write a class that has the same signature as IntMonad, but the constructor wipes your hard disc and the Do function always calls the supplied IntMonadOperation with the argument 0. Such a class would not be a monad, even though it might look a bit monady. Wiping the harddisc in the constructor breaks rule 1; always using the argument 0 breaks rules 1, 2 and 3.

In fact, you can see that any side-effect in the constructor will break rule 1 - the constructor must be "pure" for the class to be monadic. You can also see that the monad must store the value supplied to the (regular) constructor, and supply it to the first Do operation, otherwise rule 1 is broken.

Most intentional uses will automatically obey these rules, but they are there so you can verify your stuff works as expected. And, you can use these rules when you prove theorems about monads, which I'm sure you're all rushing off to do now.

But These Are Not Really Monads

No, technically a monad is an entire type system parallel to the main type system, not just a single class. I'm committing the sin of confusing classes and instances. This is more in the spirit of a true monad:

template<class T>
class Monad
{
public:
    Monad(T value) : m_value(value) { }

    template<class U>
    typedef Monad<U> (*MonadOp)(T value);

    template<class U>
    Monad<U> Do(MonadOp<U> op) const
    {
        return op(m_value);
    }

private:
    T m_value;
}

Using this we can do all kinds of operations. Sadly, the above is not valid C++.

Conclusion

If you're anything like me, you're sitting there thinking "Is that it? That's all monads are?" And the answer is, more or less, yes. My implementations above aren't worth much - I can print "Hello " and I can print "World\n", but I can't print the contents of a string variable. To do that I'd need to be able to construct IOOperation functions on-the-fly which close over the string variable, and C++ sucks too much to support stuff like that. (Anyone fancy re-writing this using functor classes? Didn't think so.)

But I hope you can see that there is nothing deeply mysterious about monads at all - the problem with understanding them comes from poor explanation, not from any deep conceptual difficulties. A monad is just something with the given interface that obeys some simple rules. That's it! The rest is just details, which rely on the core language in which monads are implemented. I'm sure those details are interesting, but you can hardly approach them until you know the basics, right? So I hope you've found this explanation illuminating! Comments are welcome below. And if you're a monad expert and I've missed something crucial, please drop me a line.