Parameter Packs and Fold Expressions

A parameter pack is simply a collection of zero or more template arguments that the compiler treats as a single entity. Whatever they are, something then has to be done with all elements within the collection. Fold expressions provide a compact way to apply a single operator across all elements of the pack.

Take the case of a function that needs to sum up an arbitrary number of integers. One way to achieve this is using recursion. However, recursion needs two distinct cases: the base case and the recursive case.

#include <iostream>

int sum()
{
    return 0;
}

// Accept a parameter pack with any number of template arguments
template <typename T, typename... Rest>
int sum(T first, Rest... rest)
{
    return first + sum(rest...);
}

int main()
{
    std::cout << sum(1, 2, 3, 4) << '\n';
    return 0;
}

The explicit function sum called with no argument is the base case. We return 0 in the case that the pack has no arguments to process so that the recursion terminates. The template version peels off one argument first from the pack and calls sum recursively with the remainder of the pack (rest...).

In each successive step, one value is added to the pack until all elements in the pack are expanded and 0 added from the base case function. Therefore, the call to sum(1, 2, 3, 4) results in the compiler generating 1 + (2 + (3 + (4 + 0))) which evaluates to 10.

The same summation can be achieved in a one liner using a fold expression. There is no need to rely on a recursive function call.

#include <iostream>

template <typename... Args>
int sum(Args... args)
{
    // Fold the parameter pack into one expression
    return (args + ... + 0);
}

int main()
{
    std::cout << sum(1, 2, 3, 4) << '\n';
    return 0;
}

Inside the function return statement, a C++ parameter pack can be expanded using a binary right fold. In the case of binary right folds, the following operator(s) must precede the ....

Therefore, (args + ... + 0) is expanded by the compiler into the equivalent of 1 + (2 + (3 + (4 + 0))).

When the pack turns out to be empty, the + 0 supplies the identity value required to complete the evaluation. All expansion happens at compile time, so there are no recursive function calls generated.

A left fold provides the inverse operation. Only the placement of the ellipsis changes.

#include <iostream>

template <typename... Args>
int sum(Args... args)
{
    return (0 + ... + args);
}

int main()
{
    std::cout << sum(1, 2, 3, 4) << '\n';
    return 0;
}

This fold expression is expansionally the same as (((0 + 1) + 2) + 3) + 4, which for addition gives the same result, but a different ordering of operations. Non associative operators will therefore produce a different result for left versus right folds.

Folds are not strictly limited to arithmetic operators. Any binary operator can be used to expand a parameter pack driven through std::cout and print out each of the values in the pack.

#include <iostream>

template <typename... Args>
void print(Args... args)
{
    (std::cout << ... << args) << '\n';
}

int main()
{
    print(10, 20, 30);
    return 0;
}

The expression (std::cout << ... << args) is evaluated as a binary left fold. This causes each element of the pack to be inserted into the stream using the stream insertion operator. The expansion is equivalent to std::cout << 10 << 20 << 30, which is then followed by << '\n' for a newline character. Because operator<< for streams always returns a reference to the same stream, the chaining naturally occurs.

With a fold containing no explicit operand in one or both operands, the empty pack scenario is catered for if the appropriate identity element is supplied. When printing with an empty pack, this identity may optionally be omitted when applying a unary fold. However, to maintain consistency, it is safer to explicitly provide an identity that matches the operator being used. The code below prints nothing at all but a single newline when used with no arguments.

#include <iostream>

template <typename... Args>
void print(Args... args)
{
    (std::cout << ... << args) << '\n';
}

int main()
{
    print();
    return 0;
}

In the case of an empty pack, the fold operation expands to nothing, leaving the final insertion of a newline to create a blank line of output. The compiled program successfully produces output and does not fall outside well formed C++.

Fold operations can also be applied to boolean values. Given the logical AND operator, all values in the parameter pack must be true if the expression is to evaluate to true.

#include <iostream>

template <typename... Args>
bool allTrue(Args... args)
{
    return (args && ...);
}

int main()
{
    std::cout << allTrue(true, true, true) << '\n';
    std::cout << allTrue(true, false, true) << '\n';
    return 0;
}

The unary right fold (args && ...) expands to true && (true && true) for the first function call, and true && (false && true) for the second. As the expression would be evaluated from left to right, short circuiting occurs identically to using ordinary chained boolean AND operations. The first call and the second print 1 and 0, respectively.

The ellipsis is simply a copy of the pack expansion mechanism found in ordinary C++ parameter packs. The ellipsis is mandatory; just writing the name of the parameter pack is a compile time error, as parameter packs themselves are not values. 

A parenthesis surrounding the entire fold expression is required by the C++ language, as C++ would otherwise have no way of knowing that an operator based expression represents a fold operation.

#include <iostream>

int sum()
{
    return 0;
}

// Accept a parameter pack with any number of template arguments
template <typename T, typename... Rest>
int sum(T first, Rest... rest)
{
    return first + sum(rest...);
}

int main()
{
    std::cout << sum(1, 2, 3, 4) << '\n';
    return 0;
}

#include <iostream>
template <typename... Values>
auto sum(Values... values)
{
    return (0 + ... + values);
}
int main()
{
    std::cout << sum(1, 2, 3, 4) << '\n';
    std::cout << sum(5, 6) << '\n';
    std::cout << sum() << '\n';
}

10
11
0