Folding Monadic Functions

In the previous two blog posts (Understanding Fold Expressions and Folding Functions) we looked at the basic usage of C++17 fold expressions and how simple functions can be folded to create a composite one. We’ll continue our stride and see how "embellished" functions may be composed in fold expressions.

First, let me define what I mean by embellished functions. Instead of just returning a simple value, these functions are going to return a generic container of the desired value. The choice of container is very broad but not arbitrary. There are some constraints on the container and once you select a generic container, all functions must return values of the same container. Let's begin with std::vector.

// Hide the allocator template argument of std::vector. 
// It causes problems and is irrelevant here.
template <class T>
struct Vector : std::vector<T> {};

struct Continent { };
struct Country { };
struct State { };
struct City { }; 

auto get_countries = [](Continent& c) -> Vector<Country> { return ... } ;
auto get_states    = [](Country& c)   -> Vector<State>   { return ... };
auto get_cities    = [](State& s)     -> Vector<City>    { return ... };

The focus of this post is folding functions like get_countries, get_states, and get_cities. As you may have noted, these functions are different from what we saw in the previous post. They don’t readily compose. The return types and argument types don’t line up. But I bet you know how to get to the cities given a Continent. Don’t you? Hold on to that intuition. It will come in handy later. In essence, my attempt is going to formalize that intuition of yours while generalizing it by leaps and bounds. Possibly, beyond recognition.

Our target here is to enable folding (a.k.a. composition) of these embellished functions similar to the compose function we saw in the previous post. We’ll call it composeM though.

Continent c;
auto cities_from_continent = composeM(get_countries, get_states, get_cities);
Vector<City> cities = cities_from_continent(c);

Let’s begin by implementing composeM using a unary left fold. Let’s use the >>= operator because we can. Of course, we’ll also need to overload >>= for our embellished functions.

template <class... Args>
auto composeM(Args&&... args)
{
  return (... >>= args);
}

template <class F, class G>
auto operator >>= (F&& f, G&& g)
{
  using FArg = arg_type_t<F>;
  using GResult = result_type_t<G>;

  return [f,g] (FArg a) -> GResult {
      using FResult = result_type_t<F>;
      GResult finalvec;
      FResult const & fvec = f(a);
      for(const auto& o: fvec) {
        const GResult& gvec = g(o);
        finalvec.insert(finalvec.end(), gvec.begin(), gvec.end());
      }
      return finalvec;
  };
}

What a nasty function is that!?

Now would be a good time to recall the intuition you had about going from a Continent to it's cities. Your intuition about implementing cities_from_continent is probably as follows. This algorithm goes all three levels in one function (with three nested loops).

1. Get a Continent from somewhere. Initialize an empty vector of cities.
2. Call get_countries (level 1)
3. Call get_states for each country (level 2)
4. Call get_cities for each state (level 3) and push_back in the vector of cities
5. Return the vector of cities

On the other hand, the overloaded >>= function implements the same intuition with only two levels at a time (as it accepts only two functions as parameters). Going three levels requires operator >>= to be called twice. C++ compiler will do that for us because we're using the fold expression in composeM. Every time compiler calls operator >>= it returns a function that's just like it received as arguments. Specifically, the returned closure is not a generic. We find out the argument type of F (FArg) and result type of G (GResult) and use them in the definition of the lambda. The returned closure is a composite because it accepts F's argument type and returns G's result type. It glues F and G together. All that ceremony is kinda important.

When operator >>= is called the first time, F is of type Continent→Vector<Countries> (i.e., get_countries) and G is of type Country→Vector<State> (i.e., get_states). The first time around, the signature of the closure is going to be Continent→Vector<State>. It's just "like" the other two. Naturally, when this closure is composed with get_cities, operator >>= works smoothly and returns a closure of type Continent→Vector<City>, which is exactly the same as cities_from_continent you intuitively had in mind.

An important difference between the direct function and the function that's the result of composition is that the composed version materializes (creates) a temporary vector every time operator >>= is called. That's an overhead. There are ways to avoid that but we may have to consider something other than std::vector. I won't discuss that here. See Range-v3.

Another Example: boost::future

So far we've looked at composition of embellished functions that accept an argument and return a vector of some type. At the beginning of the article, I suggested that there is broad set of generic containers we can choose from. Now would be a good time to select another one. How a about boost::future? We'll go through a similar exercise of compositing function that return boost::future. We'll see if there's anything common in the composition of functions that return vectors and functions that return futures.

Let's imagine there's a database that contains information about the largest countries, states, and cities in the world. As database operations are i/o bound, using futures to communicate the possibility of long execution times is a good idea. So our function look like as follows.

auto get_largest_country = [](Continent const &) -> boost::future<Country> { ... };
auto get_largest_state   = [](Country const &)   -> boost::future<State>   { ... };
auto get_largest_city    = [](State const &)     -> boost::future<City>    { ... }

If we need the largest city in the largest state of the largest country of a given continent we'll need all the three functions. As before, you have an intuition behind how to do that. May be it's something like below.

1. Get a Continent from somewhere.
2. Call get_largest_country (level 1). Wait to retrieve the result because db ops could take long.
3. Call get_largest_state for that country (level 2). Wait again.
4. Call get_largest_city for that state (level 3). Wait again.
5. Return the city

The actual code is pretty short.

auto get_largest_city_from_continent = [](Continent const &c) {
  return get_largest_city(get_largest_state(get_largest_country(c).get()).get()).get();
};

This implementation is fully synchronous and isn't optimized to use nice properties of boost::future (yet). It may remind you of function composition we saw in the previous post. However, the .get() calls in between completely mess things for us. We can't use simple function composition because it does not call .get().

Let's rewrite operator >>= that would work with functions that return boost::future. We want to compare it with that of the Vector type.

template <class F, class G>
auto operator >>= (F&& f, G&& g)
{
  using FArg = arg_type_t<F>;
  using GResult = result_type_t<G>;
    
  return [f,g] (FArg a) -> GResult {
      return g(f(a).get());
  };
}

Just like before, this function operates only two levels at a time because we pass only two functions to it. The implementation is much simpler than before because the argument functions return a boost::future and it may contain at most one value. We retrieve it using .get() and pass it on to function g.

Needless to say this implementation of >>= does not look much like the earlier (Vector) implementation of operator >>=. Is there anything common/reusable at all? Can we refactor these two functions into something reusable? Let's observe them closely under a special microscope--generic programming microscope.

Refactoring To a Generic operator >>=

Disclaimer: This section may appear a little too abstract and hand-wavy. As I already know how the refactoring is going to look like, I may skip ahead too fast and may be too hasty about some generalizations. Let me know what you think. Here we go.

Here's what I see in the implementations of operator >>=

1. Both functions are higher-order. I.e. they take functions as arguments and return a new composite function.
2. The type of the composite function depends on the types of the arguments. Specifically, the composite function is "just like" the argument functions.
3. In both cases, the argument type of the composite function is the same as that of F and the return type is the same as that of G.
4. Function f and g accept an argument of a simple type and return a value "wrapped" in a generic container. The notable difference is of the container type (Vector and boost:future, respectively). Hmm, template template parameter?
5. There's a dependency between f and g. f is invoked before g. Always. That's generic. This is key.
6. The argument passed to the composite function is passed to f (i.e., f(a)). As the return value of f is a generic container, the contained value(s) are somehow extracted and passed to g. In the case of Vector we use a for loop and in the case of boost::future, we use .get(). The specific way to get to the guts of the container is dependent on the container type. The composite function "collapses" two nested levels into one. In the case of Vector, two nested loops. In the case of boost::future, two calls to the database appear as one from outside. These things are very very specific to the container. There's no hope to generalize it. This is key too and the most hand-wavy observation.

What in the world all this means? And how we might express these observations in C++ in a reusable manner? Not all is reusable as we observed. Items #1 to #5 appear something like we can write reusable code for. #6 does not as the details depend on the container type---a template (as opposed to an instantiation of it).

Sounds like we need a template template parameter. Fine. But a template template parameter of what?

The Genius of Monad

So what we are looking for is known as a monad. That's the name it gets because mathematicians reached here first--long before we programmers existed. Let's just accept the name and move on.

Based on the commonalities listed above, we need something with nearly the same capabilities except for #6. It should allow to plug an implementation that is dependent on the container type. We are in pursuit of a monad-aware implementation of operator >>=. As #1 through #5 are reusable pieces of code, let's just copy-paste them.

template <class F, class G>
auto operator >>= (F&& f, G&& g)
{
  using FArg = arg_type_t<F>;
  using GResult = result_type_t<G>;

  return [f,g] (FArg a) -> GResult {
      return get_monad<GResult>::bind(f(a), std::move(g));
  };
}

Hopefully, it does not look too unexpected.

As you can see, this implementation has the same shape but with more flexibility. It's higher-order. Returns a closure that accepts argument of the same type as F and returns the type as G. It invokes f(a). From this point on things look different. The pluggable "interface" we use is called bind. The result of f(a) is passed to bind which is dependent on type GResult. Further function g is also passed to bind because a generic implementation won't know how to peek into the value of f(a) and invoke g on it. That's the job of bind. So there must be specializations of bind for each container template. But first, we need to identify the container template. We use a template template parameter.

Here's how get_monad looks like.

template <class T>
struct get_monad;

template <template <typename> class M, class T>
struct get_monad<M<T>> : monad<M> {};

It is a simple wrapper over the real deal: monad. The job of get_monad is to pattern-match on GResult and extract the template-name and template arguments out. It simply forwards the template-name to the monad template. I.e., In case of get_monad<Vector<City>>, monad is instantiated with just Vector as in monad<Vector>. Similarly, for the function returning boost::future, monad<boost::future> is instantiated.

That brings us to the monad template, which accepts a template template parameter.

template<template <typename> class M>
struct monad 
{ 
    template <class T, class Func>
    static auto bind(M<T>& m, Func&& func) -> result_type_t<Func>;
};

This definition only serves as an "interface" and does no work. It's completely optional. Note the signature of bind though. It accepts an argument of type M<T>, whatever M is. We'll look at two examples shortly. It also accepts a function, which must also return M<T>. Bind calls one embellished function at a time. At this point, what we really need are the specializations of this template. Here's a monad specialization for Vector.

template<>
struct monad<Vector> 
{    
    template <class T, class Func>
    static auto bind(const Vector<T>& vec, Func&& func) -> result_type_t<Func>
    { 
      // Alternatively,
      // using Outer = decltype(func(std::declval<T>()));
      using Outer = result_type_t<Func>;
      Outer outer;
      for(const T& o: vec) {
        const Outer& inner = func(o);
        outer.insert(outer.end(), inner.begin(), inner.end());
      }
      return outer;
    }
};

The bind function accepts a Vector object and a function as arguments. The job of bind is to unwrap the Vector, get the values, and pass them to the function. That's just half the story. The function itself returns a Vector for every call. bind can return only one Vector. Therefore, bind needs to combine/flatten all the Vectors into one. The outer Vector is that flat Vector, which contains all the elements from the individual Vectors received from func. Note that if if the input vector is empty, the resulting vector is also empty. Likewise, if the function func returns empty Vectors every-time, the resulting Vector is also empty. This behavior is exactly same as commonly discussed list monad.

And here's a possible implementation using boost::future.

template<>
struct monad<boost::future>
{
    template <class T, class Func>
    static auto bind(boost::future<T> fut, Func&& func) -> result_type_t<Func> { 
      return func(fut.get()); 
    }
};

Like the Vector version, future version also accepts an object of future type (i.e., the container type) and a function. The bind function extracts the value out from the future by calling get. Only bind would know how to do that. It passes it on to the function. The function itself returns a future. We simply return it. This version is fully synchronous and wait for the result of the first function to arrive before calling the next function. Recall that fut is the result of calling f(a) in operator >>=.

The bind function is not unique and it may be implemented in multiple ways. A better alternative with boost::future is to chain the result one future to a subsequent function. In fact, that's what we've been doing all along. boost::future provides a nice api called .then to chain embellished functions that return futures. Therefore, an alternative implementation of monad<boost::future>::bind could be as follows.

#define BOOST_THREAD_PROVIDES_FUTURE_CONTINUATION
#define BOOST_THREAD_PROVIDES_FUTURE_UNWRAP
#define BOOST_THREAD_PROVIDES_FUTURE
#include <boost/thread/future.hpp>

template<>
struct monad<boost::future>
{
    template <class T, class Func>
    static auto bind(boost::future<T> fut, Func&& func) -> result_type_t<Func> { 
        return fut.then([func](boost::future<T> f) mutable { 
            return func(f.get()); // calling .get here does not block.
        }).unwrap();
    }
};

The boost::future::then function is very similar to bind. The main difference is that the argument lambda to .then accepts a boost::future object as opposed the value in it. This complication is to support the possibility of futures that complete with an exception. If the first method (f) returns a future that resolves into an error, we may need to know about it. If a future resolves to an error, .get() rethrows the exception skipping all the subsequent chained functions. That's exactly what we want.

There's one more wrinkle that isn't clear in the code. .then wraps the return type of the lambda in a future. In our case the lambda returns a future itself. (e.g., future<State>). Therefore, the resulting type of .then is future<future<T>>. That does not match with that of bind, which is just future<T>. There're two ways out provided by boost::future. Either you can call .unwrap on future<future<T>> or rely on the unwrapping constructor of boost::future that auto converts future<future<T>> to future<T>. I opted for the former for clarity.

Putting It All Together

With this refactoring in place, our composeM function that does a left fold of embellished functions works just fine.

void test()
{
  auto get_cities_from_continent = composeM(get_countries, get_states, get_cities);
  auto get_largest_city_from_continent = composeM(get_largest_country, get_largest_state, get_largest_city);

  Continent c;
  auto cities = get_cities_from_continent(c);
  auto largest_city = get_largest_city_from_continent(c).get();

  std::cout << cities << "\n" << largest_city << "\n";
}

That's pretty neat. The type of the container does not matter. We successfully abstracted the details of the container type in to it's respective bind functions. For new generic containers, all we need to do is to implement a specialization of bind. Bind is the function that allows us to compose (a.k.a. chain) a set of embellished functions belonging to the same container type (monad). As long as an implementation of bind satisfying the signature exists for a container, we can use it in fold expressions. Clearly, C++ fold expressions are quite versatile. As an exercise, try implementing bind for std::optional. It's fun! Find out what monad that is.

Something's Amiss?

If you are familiar with the concept of a monad from Haskell or other languages, you know already that the monad abstraction presented above is not complete. It's missing a function called return (Haskell lingo), that accepts a unwrapped value and puts it into the chosen generic container (monad). Obviously, it is highly specific to the container used. Putting a value in a future differs significantly from putting a value in a Vector.

I'm unsure if we really need a function like return because we just have constructors in C++ to do the job. For the sake of completeness, however, I will include it.

template<>
struct monad<Vector> 
{
    template <class T>
    static Vector<std::decay_t<T>> return_(T&& t) { 
        Vector<std::decay_t<T>> vec;
        vec.push_back(std::forward<T>(t));
        return vec;
        // return { t }; // gcc hates this line.
    }
    ....
};

template<>
struct monad<boost::future>
{
    template <class T>
    static boost::future<std::decay_t<T>> return_(T&& t) { 
        return boost::make_ready_future(std::forward<T>(t)); 
    }
    ....
};

Note that the type of return_ matches with that of our embellished functions. As return_ does not do anything but "put a value into the monad", we can use it as the identity for monadic function composition. Let's use a binary left fold as a demonstration.

template <class Head, class... Tail>
struct head {
    using type = Head;   
};

template <class... Args>
auto composeM(Args&&... args)
{
  static_assert(sizeof...(Args) > 0);
  using Func = typename head<Args...>::type;
  using FArg = arg_type_t<Func>;
  auto identity = [](FArg a) { 
        return get_monad<result_type_t<Func>>::return_(a); 
  };
  return (identity >>= ... >>= args);
}

This implementation of composeM works as long as there's at least one function is passed to it. That's because composeM won't know which monad you are talking about without looking at at least one of them in the return type of the passed function. identity simply forwards its argument to the return_ function. It cheats a little in the process. It finds out the argument_type of Func (FArg). That's not strictly necessary---especially if we use generic lambdas and simply forward the argument to bind. If we do that, we need a few tweaks in operator >>=.

On a closer examination, it's clear that operator >>= does not depend on the argument type at all. It only needs to figure out the container type---the template template parameter to use to pull-in the right monad. So, GResult is all we need.

Here's the final revised version of operator >>= for folding monadic functions.

template <class F, class G>
auto operator >>= (F&& f, G&& g)
{
  //using FArg = arg_type_t<F>; not needed
  using GResult = result_type_t<G>;

  return [f=std::forward<F>(f), 
          g=std::forward<G>(g)] (auto&& a) mutable -> GResult {
      return get_monad<GResult>::bind(f(std::forward<decltype(a)>(a)), std::forward<G>(g));
  };
}

Oh, I almost forgot. The choice of operator >>= is not an accident. In Haskell >>= works the same way as our bind function. On the other hand, operator >>= is like Haskell's fish operators (>=> for right fish and <=< for left fish).

That's it! If you are still here, thank you for reading. Here's live code if you take it for a spin. This concludes the three part series on C++17 Fold Expressions. See previous posts: #1 and #2.

Appendix

Here're the templates to extract argument and result types of lambdas. They don't work with generic lambdas though.

namespace detail {

template <typename Func>
struct function_traits {
  using arg_type = typename function_traits<decltype(&Func::operator())>::arg_type;
  using result_type = typename function_traits<decltype(&Func::operator())>::result_type;
};

template <typename Func>
struct function_traits<Func &> {
  using arg_type = typename function_traits<decltype(&Func::operator())>::arg_type;
  using result_type = typename function_traits<decltype(&Func::operator())>::result_type;
};

template <typename R, typename C, typename A>
struct function_traits<R (C::*)(A)> {
  using result_type = R;
  using arg_type = A;
};

template <typename R, typename C, typename A>
struct function_traits<R (C::*)(A) const> {
  using result_type = R;
  using arg_type = A;
};

template <typename R, typename A>
struct function_traits<R (*)(A)> {
  using result_type = R;
  using arg_type = A;
};

template <class T>
using result_type_t = typename function_traits<T>::result_type;

template <class T>
using arg_type_t = typename function_traits<T>::arg_type;

}