composer_blog

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 \circ g)\) where \((f \circ 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 (fn) 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

/// 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
}

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 packaging 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);
    }
};

// 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++ 20 also introduced views, a more concise and flexible way of processing sequences. Instead of using begin-end iterator pairs, you can traverse a sequence using a range-based for-loop. Even more important is the pipeline architecture that views support, similar to what D and Rust provide. We can rewrite operator() as:

T operator()(T x) const {
    for (auto f : funs | std::views::reverse)
        x = f(x);
    return x;
}

The functions in funs are (lazily) piped into std::views::reverse so we can apply the functions in reverse order. The driver doesn’t need to change.

C++23: Full Circle

C++23 brings us back to what functional programmers are used to with std::ranges::fold_right, replacing the loop in operator() with a single ML-like statement:

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.

Addendum

Compile-Time Version

While perhaps a less common use case, if we know all the functions ahead of time, we can let the compiler do the composition. All it takes is a little template metaprogramming.

Instead of storing the functions in a vector at runtime, we can hold them in a tuple by means of variadic templates, introduced in C++11:

template<typename... Fs>
class Composer {
    std::tuple<Fs...> funs;

The ellipsis in <typename... Fs> indicates that a variable number of template type parameters can be accepted at compile time, and is called a parameter pack. To get at the actual arguments passed, we use the parameter pack of types in the context of a function parameter:

    Composer(Fs... fs)
        : funs(std::move(fs)...)
    {}

The parameter fs represents the sequence of template arguments of the corresponding types one at a time in the parameter pack of types. Fold expressions, introduced in C++17, make short work of processing static sequences using the 32 binary operators defined in the C++ language, but the function call operator is unary operator, so it appears that we may have to call upon recursion (awful pun; sorry, not sorry :-).

export module composer;

import std;

export template<typename... Fs>
class Composer {
    std::tuple<Fs...> funs;

public:
    Composer(Fs... fs)
        : funs(std::move(fs)...)
    {}

    template<typename T>
    T operator()(T x) const {
        return compose<0>(std::move(x));
    }

private:
    template<std::size_t I, typename T>
    T compose(T x) const {
        if constexpr (I == sizeof...(Fs) - 1)
            return std::get<I>(funs)(std::move(x));
        else
            return std::get<I>(funs)(compose<I + 1>(std::move(x)));
    }
};

The function call operator gets things started by calling the helper function, compose, on the first callable passed. compose in turn checks to see if the current callable object is the last one in the tuple. If not, it executes recursively on the next function in the passed sequence. When it gets to the last one (n = sizeof...(Fs) - 1), it executes that (n-1)th callable passing the original value x, thus computing \(f_{n-1}(x)\), and passes that result to the previous callable in the sequence as the recursion unwinds. Static if statements using if constexpr were also added in C++17.

import composer;
import std;

int main() {
    Composer comp(
        [](double x){ return x / 2.0; },
        [](double x){ return x * x; },
        [](double x){ return x + 1.0; }
    );
    std::cout << comp(2.0) << "\n";         // 4.5

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

Don’t Try This At Home

If you don’t mind violating a cardinal rule of operator overloading (“define operators to mimic conventional usage”), we can use a fold expression and solve the problem with two “simple” function templates and no class at all. The rule-breaking is to choose which operator to use unconventionally. Let’s use % (because it has two circles, and the composition operator in mathematics uses a circle :-).

export module composer;

import std;

// A binary "compose" operator on callables: f % g means "apply f after g"
// i.e. (f % g)(x) == f(g(x))
template<typename F, typename G>
auto operator%(F f, G g) {
    return [f = std::move(f), g = std::move(g)](auto x) {
        return f(g(std::move(x)));
    };
}

export template<typename... Fs>
auto compose(Fs... fs) {
    return (fs % ...);   // unary right fold over operator%
}

Since we are allowing lambda expressions as well as functions to be passed to compose, we need separate types for f and g (and each lambda has its own distinct type anyway). The % operator overload captures two functions at a time to be composed and returns a generic lambda (per the use of auto in the parameter; we are leaving the type of x open at this point since we have no easy way of deducing it).

The capture [f = std::move(f), g = std::move(g)] moves the two callables into the closure instead of copying them — standard practice (C++14 on) whenever a value being captured might be costly to duplicate. Also, there is no need now for if constexpr or recursion, since the fold does all the work for us. The right-fold syntax in compose (where the operator precedes the ...) distributes the % operator among the elements in the parameter pack as \(f_1 \% (f_2 \% ... (f_{n-1} \% f_n)...)\), where the \(f_i\) are the functions in the order given.

import composer;
import std;

int main() {
    auto comp = compose(
        [](double x){ return x / 2.0; },  // applied last
        [](double x){ return x * x; },
        [](double x){ return x + 1.0; }   // applied first
    );
    std::cout << comp(2.0) << "\n";       // 4.5

    auto comp2 = compose(
        [](std::string s){ return s + "s"; },
        [](std::string s){ return s + "'"; }

    );
    std::cout << comp2(std::string("Vernor")) << "\n"; // Vernor's
}

The call to compose that defines comp above creates a lambda expression holding f1 % (f2 % f3) waiting to be called with argument x that will later compute f1(f2(f3(x))), where the f’s stand for the three lambdas passed to the first call to compose in the order given.