Composing Functions in Modern C++

C++23 Code Capsules

Mathematicians and programmers alike have always known that functions are things you can do things with, not just things you call. One of the most natural operations on functions is composition: given f and g, form the new function (f ∘ g) where (f ∘ g)(x) = f(g(x)). Chain enough of these together and you have a pipeline — a sequence of transformations applied one after another.

Functional programmers have known this for decades. In Standard ML, folding a list of functions over an initial value is idiomatic and concise:

(* ML: apply a list of functions right-to-left *)
fun compose fs x = foldr (fn (f, acc) => f acc) x fs

foldr processes the list from the right, threading an accumulator through each function in turn. The result is function composition expressed as a fold — \(f_1(f_2(...f_n(x)...))\) — and the combining function takes (element, accumulator) in right-to-left order.

C++, being based on a procedural language that put performance first, took a longer road to arrive at the same idea. But arrive it did. This capsule traces that journey across three standards, building a reusable Composer class that grows cleaner at each step.

C++11: A Working Solution

Here is a first cut, written in C++11:

/// C++11 version: Use function T<T> to compose a vector of functions into a single function object.
#include <algorithm>
#include <functional>
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;

template <typename T>
class Composer
{
    vector<function<T(T)>> funs;

public:
    Composer(const vector<function<T(T)>> &fs) : funs(fs) {}
    T operator()(T x) const
    {
        auto apply = [](T acc, function<T(T)> f)
        { return f(acc); };
        return accumulate(rbegin(funs), rend(funs), x, apply);
    }
};

struct g
{
    double operator()(double x) { return x * x; }
};

int main()
{
    auto f = [](double x)
    { return x / 2.0; };
    const Composer<double> comp({f, g(), [](double x){ return x + 1.0; }});
    cout << comp(2.0) << "\n"; // 4.5

    const Composer<string> comp2({[](string s){ return s + "s"; }, [](string s){ return s + "'"; }});
    cout << comp2("Vernor") << "\n"; // Vernor's
}

The core of the class is this line:

return accumulate(rbegin(funs), rend(funs), x, apply);

Walking the vector in reverse and folding left is equivalent to folding right — it applies the last function first, then the second-to-last, and so on. This is exactly ML’s foldr in disguise, expressed through std::accumulate and reversed iterators. It works, but the disguise is unfortunate: the intent is a right fold, but it isn’t crystal clear for the casual reader..

C++20: Packaging the Class

C++20 allows to package the class as a reusable module. (I realize it is not big enough to warrant a module, but I’m excited that I finally have modules working, so please indulge me!):

// C++20 version: Make a module
export module composer;

import std;

export template <typename T>
class Composer
{
    std::vector<std::function<T(T)>> funs;

public:
    Composer(const std::vector<std::function<T(T)>> &fs) : funs(fs) {}
    T operator()(T x) const
    {
        auto apply = [](T acc, std::function<T(T)> f)
        { return f(acc); };
        return std::accumulate(std::rbegin(funs), std::rend(funs), x, apply);
    }
};

The driver now becomes:

// C++20 Driver
import composer;
import std;

using std::cout;
using std::string;
using std::vector;

struct g
{
    double operator()(double x) { return x * x; }
};

int main()
{
    auto f = [](double x) { return x / 2.0; };
    const Composer<double> comp({ f, g(), [](double x) { return x + 1.0; } });
    cout << comp(2.0) << "\n"; // 4.5

    const Composer<string> comp2({ [](string s) { return s + "s"; }, [](string s) { return s + "'"; } });
    cout << comp2("Vernor") << "\n"; // Vernor's
}

C++23: Full Circle

C++23 brings us back to what functional programmers are used to with std::ranges::fold_right, replacing the call to std::accumulate(rbegin...):

T operator()(T x) const {
    return std::ranges::fold_right(funs, x, [](auto f, auto acc){ return f(acc); });
}

Notice the argument order in the lambda: (element, accumulator). This is the same order as ML’s foldr combining function — fn (f, acc) => f acc. That is not a coincidence. C++ has absorbed the idea, and the interface reflects it.

This is the direction modern C++ has been moving for some time. Ranges, folds, modules — these are not disconnected features. They are the pieces of a language that is gradually adopting powerful ideas in its own idiom, an idiom that has had a sometimes-hard-to-follow syntactic path, but has delivered performance and code compatibility without peer.

What goes around comes around.