Folding Expressions

People familiar with the new features C++11 brought to the C++ programming language should know what a variadic template is and why they’re important. Variadic templates can have a variable number of parameters of any type:

template <typename... Types> class tuple;

This not only brings type safety to the code but also ensures that all the variadic arguments handling is performed at compile-time. Before their introduction, in order to have a template accepting a variable number of template parameters, programmers were used to write verbose code like:

template<typename T0>
void function( T0 arg0 );

template<typename T0, typename T1>
void function( T0 arg0, T1 arg1 );

template<typename T0, typename T1, typename T2>
void function( T0 arg0, T1 arg1, T2 arg2 );

template<typename T0, typename T1, typename T2, typename T3>
void function( T0 arg0, T1 arg1, T2 arg2, T3 arg3 );

...

Template parameter packs went hand-in-hand with variadic templates and together with constant expressions they enabled a recursive-like style of coding to create more complex compile-time operations:

#include <iostream>
#include <array>

template<size_t... Is> struct seq{};
template<size_t N, size_t... Is>
struct gen_seq : gen_seq<N-1, N-1, Is...>{};
template<size_t... Is>
struct gen_seq<0, Is...> : seq<Is...>{};

template<size_t N1, size_t... I1, size_t N2, size_t... I2>
// Expansion pack
constexpr std::array<int, N1+N2> concat(const std::array<int, N1>& a1, 
        const std::array<int, N2>& a2, seq<I1...>, seq<I2...>){
  return {{ a1[I1]..., a2[I2]... }};
}

template<size_t N1, size_t N2>
// Initializer for the recursion
constexpr std::array<int, N1+N2> concat(const std::array<int, N1>& a1, 
                                       const std::array<int, N2>& a2){
  return concat(a1, a2, gen_seq<N1>{}, gen_seq<N2>{});
}

int main() {
    constexpr std::array<int, 3> a1 = {{1,2,3}};
    constexpr std::array<int, 2> a2 = {{4,5}};

    constexpr std::array<int,5> res = concat(a1,a2);
    for(int i=0; i<res.size(); ++i)
        std::cout << res[i] << " "; // 1 2 3 4 5

    return 0;
}

Exploiting a constexpr overload of the operator[] the code above generates an integer sequence, aggregate-initializes an std::array and concatenates the input arrays at compile time (details of the operations involved are available at this link).

The integer generation sequence construct was then provided by the standard library itself in C++14 with std::integer_sequence.

These features allowed new ways to exploit templates, anyway parameter packs could only be used and expanded in a strictly-defined series of contexts. For instance, something like the following wasn’t allowed:

template<typename T>
void printer(T arg) {
    std::cout << arg << " ";
}

template<typename... Args>
static void function(Args &&... args) {
    (printer(std::forward<Args>(args)) , ...);
}

Anyway one of those restricted contexts was brace-init-lists, therefore workarounds to have parameter packs be expanded were immediately deployed:

template<typename T>
void printer(T arg) {
    std::cout << arg << " ";
}

template<typename... Args>
static void function(Args &&... args) {
    // Expand the pack into a brace-init-list while discarding the return
    // values and filling an unused array
    int unusedVar[] = { 0, 
              ( (void) printer(std::forward<Args>(args)), 0) ... };
}

C++17 ~ fold expressions

C++17, scheduled by 2017 at the time of writing, will introduce fold expressions into play and significantly broaden parameter packs scopes of use (cfr. N4191 paper).

As listed in cppreference, at the time of writing, there are four kinds of fold expressions:

• Unary right fold

  ( pack op ... )

• Unary left fold

  ( ... op pack )

• Binary right fold

  ( pack op ... op init )

• Binary left fold

  ( init op ... op pack )

being their respective expansions:

• E_1 op (... op (E_N-1 op E_N))

• ((E_1 op E_2) op ...) op E_N

• E_1 op (... op (E_N−1 op (E_N op init)))

•  (((init op E_1) op E_2) op ...) op E_N

In binary folds the op operators must be the same and init represents an expression without an unexpanded parameter pack (e.g. the init value for the expanded expression).

With fold expressions writing a printer construct becomes straightforward:

#include <iostream>

template<typename F, typename... T>
void for_each(F fun, T&&... args)
{
    (fun (std::forward<T>(args)), ...);
}

int main() {
     for_each([](auto i) { std::cout << i << " "; }, 4, 5, 6); // 4 5 6
}

The sample above uses fold expressions together with the comma operator to create a simple function that calls the provided lambda per each one of the supplied arguments with perfect forwarding.

A caveat relative to the previous example though: unary right fold expressions and unary left fold expressions applied with the comma operator do yield different expressions but their evaluation order remains the same, e.g.

#include <iostream>
#include <memory>

template<typename F, typename... T>
void for_each1(F fun, T&&... args)
{
    (fun (std::forward<T>(args)), ...);
}

template<typename F, typename... T>
void for_each2(F fun, T&&... args)
{
    (..., fun (std::forward<T>(args)));
}

int main()
{
     for_each1([](auto i) { std::cout << i << " "; }, 4, 5, 6); // 4 5 6
     std::cout << std::endl;
     for_each2([](auto i) { std::cout << i << " "; }, 4, 5, 6); // 4 5 6
}

It has to be noted that one of the main reasons fold expressions were accepted as a C++17 proposal is because of their use in concepts:

template <typename T>
  concept bool Integral = std::is_integral<T>::value;

template <Integral... Ts> // A constrained-parameter pack
  void foo(Ts...);

template <typename... Ts>
  requires Integral<Ts>... // error: requirement is ill-formed
void foo(Ts...);

The problem boiled down to the same issue we talked of some paragraphs ago: the parameter pack cannot expand in that context. Fold expressions provide an elegant and effective way to deal with this issue instead of resorting to other constexpr machineries to ensure requirements are met:

template<typename... Ts>
  requires (Integral<Ts> && ...)
void foo(Ts...);

References and sources:
N4191 – Folding expressions
cppreference
constexpr flatten list of std::array into array
Variadic template pack expansion
Why doesn’t a left fold expression invert the output of a right fold expression

Thanks to Marco Arena and Andy for the quick review of this article.