The Vector Monad in C++, Without the Ugly Stuff

Now that we’ve got our feet wet and have a feeling of the vector monad in C++, let’s use modern C++ to make a more elaborate implementation of the vector monad, but that leads to cleaner code.

You’ll note that the way of thinking here has a lot in common with the optional monad in C++, even though it was focused on multiple error handling while the vector monad aims at chaining functions returning multiple arguments.

Passing along multiple values

For the sake of the example, let’s take three functions that take and return integers:

int f1(int a);
int f2(int b, int c);
int f3(int d);

These functions, like all normal functions in the world of functions, take one version of their parameters.

But what if there were several versions of their parameters? Or, said differently, what if we had a vector of values for each argument, and wanted to get out of the function a vector of results, that would contain the results of the function applied to every possible combination of arguments?

(Little legal note for the functional aficionados: Okay, this is not a monad, it’s an applicative (thanks Quentin). But the use case is interesting and we’ll get to the actual monad in section 2 anyway!)

The way I want to show you is to encapsulate the mechanism of applying a function to all possible combinations of arguments. If you’re a regular reader of Fluent C++, doesn’t this sound familiar to you? Of course! The Cartesian product range adaptor!!

Indeed, cartesian_product, now available in the range v3 library, is exactly made for that job: applying a function to all the possible combinations of elements in several ranges.

Let’s use it to encapsulate the mechanism:

template <typename Res, typename ... Args>
auto make_multiple(Res (*f)(Args...))
{
    return [f](std::vector<Args> const& ... args) -> std::vector<Res>
    {
        std::vector<Res> results;
        ranges::push_back(results, ranges::view::cartesian_product(args...) | ranges::view::transform(tupled_args(f)));
        return results;
    };
}

Don’t panic, here is how to read this code:

make_multiple is a function that takes a function f, and returns another function (well, a lambda to be precise). By the way this particular implementation only supports functions, and not callable objects in general (and thank you Vittorio for your suggestions on that topic).

The lambda that it returns takes vector<Args>s as arguments where f only took Argss, and it returns a vector<Res> where f only returned one Res.

ranges::view::cartesian_product(xs...)  this cartesian product is a range view over all the possible combinations of the elements in the variadic pack of vectors xs.... These combinations are piped through to a range::view::transform to apply the function on each on of them. If you’re not into ranges yet, it’s a very popular library you really want to get familiar with, because it is likely the future of the STL.

Finally there is this tuple_args thing. If you’re not curious about it it’s fine, move on to the next paragraph, you won’t need it. But if you are curious about it, it is necessary because cartesian_product produces a view over a range of which each element represents a combination of values. So each of these elements is a tuple. But f can’t be applied directly on a tuple, so tupled_args forwards the elements of the tuples as arguments of f. If you’re still curious, you can unveil the following code to see my implementation of tupled_args:

template<typename Function, typename Args, size_t... index>
auto tupled_args_impl(Function func, Args const& args, std::index_sequence<index...>)
{
    return func(std::get<index>(args)...);
}

template<typename Res, typename... Args>
auto tupled_args(Res(*func)(Args...))
{
    return [func](std::tuple<Args...> const& args)
    {
        return tupled_args_impl(func, args, std::make_index_sequence<sizeof...(Args)>{});
    };
}

And here is how make_multiple can be used:

auto multiple_f1 = make_multiple(f1);
auto multiple_f2 = make_multiple(f2);

std::vector<int> results = multiple_f3(multiple_f2(multiple_f1({1, 2, 3}), multiple_f1({3, 4, 5})));

Vectors in, vectors out, and what’s best: the implementation of f is unchanged.

Creating multiplicity

Until now we’ve dealt with passing along multiple parameters to generate multiple return values. Now how about generating multiple values directly in our functions taking a single set of parameters? Multiplicity has to start somewhere!

Let’s modify f2 so that it takes one version of each of its two parameters, and returns a vector of resulting values:

int f1(int a);
std::vector<int> f2(int b, int c);
int f3(int d);

Can you think of a way to adapt the make_multiple function so that it still works with the new version of f2? More precisely, how to keep chaining up calls to multiple_f1, multiple_f2 and multiple_f3 so that they can still pass along vectors of values, but for each of the values coming out of multiple_f1, multiple_f2 would generate several results? So multiple_f2 would produce a big big vector in a way.

Before reading further, take a moment to think about how you would go about implementing this.

Maybe re-read the instructions, and even the article from the beginning, and even the full story starting in the previous post if you feel it’s necessary. It takes time to get accustomed to this way of programming (at least it did for me!).

Done?

Okay, so here is one way to go about it: each application of f on a combination of arguments returns a vector, so to put all the results into one single vector we need to concatenate all the results.

EDIT: Quentin Duval made many suggestions to improve this implementation, for which I’m very grateful. I haven’t processed them all yet but one of them is that the range v3 implements the desired concatenation with the join view adaptor, which we’ll use here:

template <typename Res, typename ... Args>
auto make_multiple(std::vector<Res> (*f)(Args...))
{
    return [f](std::vector<Args> const& ... args) -> std::vector<Res>
    {
        std::vector<std::vector<Res>> functionResults;
        ranges::push_back(functionResults, ranges::view::cartesian_product(args...) | ranges::view::transform(tupled_args(f)));
        return functionResults | ranges::view::join;
    };
}

With this we can write the chain of functions that pass on and creates multiple arguments and return values:

auto multiple_f1 = make_multiple(f1);
auto multiple_f2 = make_multiple(f2);
auto multiple_f3 = make_multiple(f3); 

std::vector<int> results = multiple_f3(multiple_f2(multiple_f1({1, 2, 3}), multiple_f1({3, 4, 5})));

Let’s take a step back

Okay, we’re at the end of a 4 posts-series on functional programming concepts applied to C++. Two were on optional and multiple error handling, and the other two were on vector and dealing with multiple values.

This way of programming is unusual in C++. But I believe that borrowing the concepts of functional programming can nudge us towards the terse and expressive writing these languages tend to have. Now how exactly to implement these concepts in C++ is still open to the question. I’ve shown some implementations (special thanks to Jacek), but there are surely better ones out there, or waiting to be written.

Now what do YOU think? To which extent do you use functional programming principles in your C++ code? Do you use monads? Do you use others than optional and vector? Share your experience with us, and make everyone benefit from it!

Don't want to miss out ? Follow:   
Share this post!