Fold Expressions

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 + ...)
2

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. For now, a simplified explanation is that we can imagine 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}
11

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

1Result: 35
2

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 form of that, but we have more options.

In this example, our fold expression uses the square of each value in the parameter pack, resulting in an expression like (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}
11

1Result: 14
2

Below, we send every value 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}
17

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

Folding Over the Comma Operator

Often, we will simply want to iterate over every parameter in our container. A fold expression can help us here, too. In these scenarios, we don’t care what the fold expression returns, we only care about the side effect.

To do this, we can use the comma operator , within our fold expression. Here, we pass every parameter in our pack into a function:

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

1Hello World
2

We can shorten this using 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(){ Fold("Hello", "World"); }
14

1Hello World
2

In this case, the Args we pass to the lambda is the same as the Args parameter of the outer Fold expression.

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

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

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

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

1Hello World
2

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

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

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

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:

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

Binary Folds

We have the option of adding an additional 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 using 0 as the initial value:

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

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

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

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

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

Binary folds have two main uses. First, they succinctly allow us to add support for empty parameter packs.

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(); // 0 
13  UnaryFold();
14}
15

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

Secondly, fold expressions do not need to be arithmetic. We can fold over any operator, and binary fold expressions give us additional options here.

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(){ Fold("Hello ", "World"); }
9

1Hello World
2