What Happens in Monads Stays in Monads

There are moments in life when you have to take a stance. You know countless people already tried and possibly succeeded in doing something, but you feel the urge to try it yourself.

So yesterday I attended the Milan C++ Meetup by Marco Arena, presented in a very entertaining and well-organized way, what’s new in C++23. Everything was fine until Marco presented the std::expected template and its “monadic operations”. Now it was in the context of a much wider presentation and there was no time to go into details, but I got the impression that the C++ community has a bit of an ad-hoc approach to monads. I mean C++98 failed to recognize that containers are monads, C++11 failed to recognize that std::future is a monad, C++17 failed to recognize that std::optional is a monad, and C++20 failed to recognize that coroutines are monads. You can see a pattern there.

I believe that the problem lies in the ad-hoc approach. The standardization committee introduces X in the C++ standard, and only later becomes aware that some operations would be useful, and so add them in the next standard.

The daunting task I’m trying to accomplish with this post is to explain what a monad is and how that applies to various programming objects, in the hope to give enough motivation to approach monadic operations in a uniform and coherent way. There is a wonderful talk on this subject applied to C++ by Bartosz Milewski, consider watching his video regardless of this post.

From a programmer’s perspective the best way to imagine a monad is by using the interface concept. A monad is a generic interface that can be implemented by some types. From this point of view the monad is defined by three properties:

• the generic type (e.g. a monad of int, a monad of strings, …);
• a constructor method that accepts a value of the generic type and returns a monad containing such a value;
• a transformation method that accepts a function taking a value of the generic type and returning a monad and a potentially different type.

According to monad literature (which originated in academic papers on algebra) the constructor method is called return (sometimes unit), while the transformation method is called bind.

If we want to define this using C++ syntax, a monad would be something like:

/* A C++ Monad Interface */

template<typename T>
class Monad
{
  public:
    static Monad<T> Return( T&& t );

    template<typename U>
    Monad<U> Bind( std::function<Monad<U>(T)>(T&&) ) const;
};

As a seasoned C++ programmer, the first question that comes to mind is – “how the heck do I get the value out of the monad?”

Well, indeed you don’t. What enters a monad, there it stays. If you want to perform computations on the value, you need to use the bind method. This method gets the value and can operate directly on it¹.

Now, to be more precise, a Monad is a specialized version of another algebraic concept named Functor (which, regretfully, has nothing to do with the concept associated with the same word in the C++ context). As programmers, we can think of a functor of a generic interface that has three properties:

• the generic type (a functor of int, strings, …);
• a constructor method that given a value of the generic type produces a functor with that value;
• a transformation method (called morphism) that, given a function U f(T), transform a functor of T into a functor of U applying the function to the functor content.

At first sight, it may seem not that different from the monad definition. Let’s have a look at pseudo C++ code to define the Functor interface:

/* A C++ functor interface */
template<typename T>
class Functor
{
  public:
    Fuctor( T&& t );

    template<typename U>
    Functor<U> Morph( std::function<U(T)> f ) const;
};

The difference is in the Morph/Bind method – Morph transforms a T into a U, without adding any structure – the structure of the Functor is preserved. While Bind transforms a T into a Monad<U> wrapping the result into a Monad structure.

In functional programming languages, Bind is usually called flatMap², while Morph is usually called map. In C++ the map function is approximately implemented by the std::transform function.

Now let’s shift gears. Up to now, seen in isolation, these abstractions don’t seem to do much. And that’s true since the power of monads is achieved by combining them. Monads are a powerful tool to chain computations together.

Having seen only std::optional and std::expected, you may think this is just disguised error handling, saving some explicit ifs in your code. This is just a limited view – the exact behavior of the chaining operation depends on the specific monad. E.g. options are chained so that an empty option skips the invocation of the function passed to bind. Futures executes the function passed to bind when the value is available. Containers of a type are transformed into containers of another type when the morph is applied.

But is it enough to have a flatMap method to call it a Monad? Indeed no. You can’t write any arbitrary implementation of flatMap. For a Monad to be a Monad, Return, and Bind must obey the so-called Monad laws:

1. Constructing a monad from x, then invoking flatMap(f), must be equivalent to f(x);
2. If you flatMap a monad m with the Return function, you get m.
3. flatMap must be associative, i.e. given the monad m, and the functions f and g, m.flatMap( x => f(x).flatMap(g); )³ must be equivalent to M(a).flatMap(f).flatMap(g).

Although chaining is good, it indeed tends to become a little bloated when you want to chain several functions (and C++ lambda syntax surely doesn’t help). Taking the example from Marco’s talk:

return find_coupon(sv)
  .and_then( check_active )
  .and_then( [&](const auto& c ) {
    return check_expired(ci,ts);
  })
  .transform( [](const auto& ci ) {
    return ci.amount;
  });

For this reason, functional programming language provides a tool for a more compact and readable form. Haskell has the do notation, while Scala has the for-comprehension. I’ll use the Scala version which I find a bit more readable for those that doesn’t know the language:

for{
  coupon <- find_coupon(sv)
  activeCoupon <- check_active( coupon )
  unexpiredCoupon <- check_expired( activeCoupon )
}
yield unexpiredCoupon.amount

As you can see, the code is much more readable even if you are unfamiliar with the syntax. Also, this construct can be applied to any monad regardless of the specific implementation.

To recap, monads are a much wider subject than you may reckon by staying only in the C++ domain. Monads provide a convenient abstraction to chain operation on a wide variety of structures and concepts. Failing to recognize this generality, will result in half-hearted ad-hoc solutions. For this reason, full concepts from the functional programming paradigm must enter the C++ community making the standard committee more sensitive on the subject.

1. This is true from the algebra perspective. We are programmers, and we need to come to a pact with the hard constraints, the deadlines, and the readability. For this reason, functional languages add methods to retrieve the value from the monad (such as get_or_else). These methods must be considered shortcuts, not part of the monads tool. ↩︎
2. Like it wasn’t enough to misuse the term ‘functor’, yesterday I discovered that the C++23 standard decided that flat_map is a completely unrelated thing to what functional programming folks use that term for ↩︎
3. I tried to write the lambda in C++, but the expression became too obscure. So you can read x => f(x).flatMap(g) as equivalent C++ code: []( auto&& x ){ return f(std::forward<decltype(x)>(x) ).flatMap(g); }. ↩︎