Fold Expression

C++17 introduced fold expressions, which provide a shortened syntax to implement simple recursive algorithms that act on a parameter pack. A fold expression looks like this:

1(Args + ...)

It has four components:

• A set of parenthesis, ( and )
• An expression involving a parameter pack. In this example, we’ve assumed our parameter pack is called Args
• An operator - in this example, we’ve used +
• A set of ellipses - ...

We’ll delve into the specific behavior of parameter packs throughout this lesson.

Using Fold Expressions

When using a fold expression, we can imagine it inserting the operator between every object in the parameter pack and returning the result of that expression.

In the following example, we use a parameter pack containing the integers 5, 10, and 20. Our fold expression uses the + operator, so our expression unpacks to something equivalent to 5 + 10 + 20.

1#include <iostream>
2
3template <typename... Types>
4auto Fold(Types... Args){
5  return (Args + ...);
6}
7
8int main(){
9  std::cout << "Result: " << Fold(5, 10, 20);
10}

Our result is the sum of everything in the parameter pack:

1Result: 35

The operand we use in a fold expression can be any expression involving the parameter pack. Simply using Args in isolation is the most obvious example of such an expression, but we can get more complex.

In this example, our fold expression uses the square of each value in the parameter pack, resulting in an expression equivalent to (1*1) + (2*2) + (3*3):

1#include <iostream>
2
3template <typename... Types>
4auto Fold(Types... Args){
5  return ((Args * Args) + ...);
6}
7
8int main(){
9  std::cout << "Result: " << Fold(1, 2, 3);
10}

1Result: 14

Below, we send every value of our parameter pack into a function and use the function’s return value in our fold expression. In this case, our function just logs the value, and then returns it unmodified:

1#include <iostream>
2
3int Log(int Arg){
4  std::cout << "Arg: " << Arg << '\n';
5  return Arg;
6}
7
8template <typename... Types>
9auto Fold(Types... Args){
10  return (Log(Args) + ...);
11}
12
13int main(){
14  int Result{Fold(5, 10, 20)};
15  std::cout << "Result: " << Result;
16}

1Arg: 5
2Arg: 10
3Arg: 20
4Result: 35

Folding Over the Comma Operator

Often, we will simply want to iterate over every parameter in our container - we may not care what the fold expression returns. For this, we can fold over the comma operator ,

The following example is similar to the previous, except instead of logging and summing our parameters, we only want to log them. As such, we can replace the + operator with , and change our return types to void:

1#include <iostream>
2
3template <typename T>
4void Log(T Object){
5  std::cout << Object << ' ';
6}
7
8template <typename... Types>
9void Fold(Types... Args){
10  (Log(Args), ...);
11}
12
13int main(){
14  Fold("Hello", "World");
15}

In this case, we can imagine the expression (Log(Args), ...); expanding to Log("Hello"), Log("World"); to generate the output:

1Hello World

1template <typename... Types>
2void Fold(Types... Args){
3  (static_cast<void>(Log(Args)), ...);
4}

Using Lambdas

We can replace our Log() function from the previous example with a lambda, which we pass Args to:

1#include <iostream>
2
3template <typename... Types>
4void Fold(Types... Args){
5  (
6    [](auto& Arg){
7      std::cout << Arg << ' ';
8    }(Args),
9    ...
10  );
11}
12
13int main(){
14  Fold("Hello", "World");
15}

1Hello World

In this case, the Args we pass to the lambda is the same as the Args parameter of the outer Fold() function:

1template <typename... Types>
2void Fold(Types... Args){
3  (
4    [](auto& Arg){
5      std::cout << Arg << ' ';
6    }(Args),
7    ...
8  );
9}

As such, this example can be simplified by having the lambda capture Args directly from the outer function’s scope using [&Args] or simply [&] as the capture group:

1[&](auto& Arg){
2  std::cout << Args << ' ';
3}(Args)

This allows us to remove both the parameter list from our lambda, and the argument when we invoke it:

1[&]{
2  std::cout << Args << ' ';
3}()

Let’s put everything together:

1#include <iostream>
2
3template <typename... Types>
4void Fold(Types... Args){
5  (
6    [&]{ std::cout << Args << ' '; }(),
7    ...
8  );
9}
10
11int main(){
12  Fold("Hello", "World");
13}

1Hello World

Left Folds and Right Folds

There are two ways a fold operation can be implemented - these are generally called left folds and right folds. The difference is the order in which the parameters in the parameter pack are combined to generate the return value.

We control the direction of the fold by reordering the components of the fold expression:

1template <typename... Types>
2auto LeftFold(Types... Args){
3  return (... + Args);
4}
5
6template <typename... Types>
7auto RightFold(Types... Args){
8  return (Args + ...);
9}

For some operators, the fold direction doesn’t matter. For example, addition is associative - that is, given a list of numbers, their sum will be the same regardless of the order in which the numbers are added.

But that is not always the case. For example, subtraction is not associative. The following example shows a left fold and right fold in that context:

1#include <iostream>
2
3template <typename... Types>
4auto LeftFold(Types... Args){
5  return (... - Args);
6}
7
8template <typename... Types>
9auto RightFold(Types... Args){
10  return (Args - ...);
11}
12
13int main(){
14  std::cout << "(5 - 10) - 20 = ";
15  std::cout << LeftFold(5, 10, 20);
16
17  std::cout << "\n5 - (10 - 20) = ";
18  std::cout << RightFold(5, 10, 20);
19}

Even though the parameter pack is the same in each case, each fold type composes the operations in a different order, thereby generating different return values. LeftFold() returns -25, whilst RightFold() returns 15:

1(5 - 10) - 20 = -25
25 - (10 - 20) = 15

Binary Folds

We have the option of adding a second operand to a fold expression, thereby creating a binary fold. This additional operand is sometimes referred to as the "initial value". Below, we demonstrate the syntax using 0 as the initial value:

1template <typename... Types>
2int BinaryFold(Types... Args){
3  return (0 + ... + Args);
4}

1template <typename... Types>
2int BinaryFold(Types... Args){
3  return (0 + ... - Args);
4}

1error: '-' in a binary fold expression
2both operators must be the same

Like unary folds, binary folds have two variants - commonly called right and left, which we can control by reordering the components of our fold expression:

1#include <iostream>
2
3template <typename... Types>
4int BinaryLeftFold(Types... Args){
5  return (0 - ... - Args);
6}
7
8template <typename... Types>
9int BinaryRightFold(Types... Args){
10  return (Args - ... - 0);
11}
12
13int main(){
14  std::cout << "((0 - 5) - 10) - 20 = ";
15  std::cout << BinaryLeftFold(5, 10, 20);
16
17  std::cout << "\n5 - (10 - (20 - 0)) = ";
18  std::cout << BinaryRightFold(5, 10, 20);
19}

1((0 - 5) - 10) - 20 = -35
25 - (10 - (20 - 0)) = 15

Binary folds have two main uses. First, they allow us to handle empty parameter packs without causing compilation errors.

In the following example, the binary fold function will return 0 when called with no arguments, whilst the unary fold function will cause a compilation error:

1template <typename... Types>
2int BinaryFold(Types... Args){
3  return (0 + ... + Args);
4}
5
6template <typename... Types>
7int UnaryFold(Types... Args){
8  return (... + Args);
9}
10
11int main(){
12  BinaryFold(); // Returns 0 
13  UnaryFold(); // Compilation error 
14}

1error: a unary fold expression over '+' must have a non-empty expansion
2see reference to function template instantiation 'int UnaryFold<>(void)'

Secondly, fold expressions are not limited to arithmetic operations. We can fold over any operator, and binary fold expressions provide additional flexibility in this regard.

The following example logs everything in a parameter pack, using << as the operator, and std::cout as the initial operand:

1#include <iostream>
2
3template <typename... Types>
4void Fold(Types... Args){
5  (std::cout << ... << Args);
6}
7
8int main(){
9  Fold("Hello ", "World");
10}

1Hello World

The previous example works because the initial expression will be std::cout << "Hello ". As we’ve seen in all our previous examples of terminal logging, this expression returns a reference to the std::cout object, allowing us to chain more values to the terminal.

The previous fold expression is effectively equivalent to:

1(std::cout << "Hello ") << "World";

If our parameter pack had a third value, like the string "!!!", our fold expression would be:

1((std::cout << "Hello ") << "World") << "!!!";

This pattern continues for any number of parameters.

Summary

In this lesson, we explored fold expressions, a C++17 feature that can make working with parameter packs easier. The key points to remember include:

• C++17 fold expressions combine a parameter pack and an operator, separated by the ... syntax.
• Fold expressions can be either unary (using one operand - the parameter pack) or binary (using two operands - the parameter pack and an initial value).
• Using fold expressions with arithmetic operations to perform calculations on parameter packs.
• The concept of left folds and right folds and their significance in operation ordering.
• How to use the comma operator in fold expressions for iterating over parameter packs and executing side effects.
• Addressing the potential issue of overloaded comma operators in fold expressions.
• The utility of binary folds in handling empty parameter packs and their application beyond arithmetic operations, including logging with std::cout.

Next Lesson

Perfect Forwarding and std::forward

An introduction to problems that can arise when our functions forward their parameters to other functions, and how we can solve those problems with std::forward

ContinueView Course