Jonathan Boccara's blog

Tweet

C++ Fold Expressions 101

Published March 12, 2021 - 0 Comments

Daily C++

C++17 brought fold expressions to the language. This interesting feature allows to write expressive code, that almost seems magical.

Here is a two-posts recap on how fold expressions work (this post) and how they can improve your code (the next post).

Fold expressions

A fold expression is an instruction for the compiler to repeat the application of an operator over a variadic template pack.

Let’s take an example. A very basic one and with a questionable usefulness, but one that illustrates how fold expressions work. A toy example, if you will. We’ll get to more interesting examples in the next post.

The example is a sum function, that computes the sum of all its parameters and returns it:

template<typename... Values>
auto sum(Values const&... values)
{
    // code here
}

How would you implement this function?

If we had to write it with 2 parameters it would look like this:

template<typename Value1, typename Value2>
auto sum(Value1 const& value1, Value2 const& value2)
{
    return value1 + value2;
}

With 3 parameters it would look like this:

template<typename Value1, typename Value2, typename Value3>
auto sum(Value1 const& value1, Value2 const& value2, Value3 const& value3)
{
    return value1 + value2 + value3;
}

With 4 parameters, it would look like this:

template<typename Value1, typename Value2, typename Value3, typename Value4>
auto sum(Value1 const& value1, Value2 const& value2, Value3 const& value3, Value4 const& value4)
{
    return value1 + value2 + value3 + value4;
}

How about with a parameters pack? To implement sum with generic code, we can use a fold expression:

template<typename... Values>
auto sum(Values const&... values)
{
    return (values + ...);
}

Note the two aspects of its syntax:

  • the fact that it is surrounded by parentheses,
  • the + ... that creates the repetition of the application of the operation.

This is a fold expression. At this point you may wonder why all this technology, why not just write the sum at the call site. But for that too, we’ll get to more interesting examples in the next post, that will be published in a few days.

Before that, we need to master the mechanics of the fold expressions, and there is another aspect to it: associativity.

The associativity of fold expressions

Suppose we call our sum function with 1, 2 and 3:

sum(1, 2, 3)

Then the code generated by the template resolution is equivalent to this:

int sum(int const& value1, int const& value2, int const& value3)
{
    return value1 + value2 + value3;
}

Well, this is not accurate. Because the expression value1 + value2 + value3 doesn’t mean anything to the compiler.

Indeed, operator+ is a function that takes 2 parameters. In value1 + value2 + value3, there are 3 parameters, and two calls to the operator. This is not something the compiler can execute.

To give it sense, we have to decide which operator gets called first. Is it the one on the left?

int sum(int const& value1, int const& value2, int const& value3)
{
    return (value1 + value2) + value3;
}

This would be left associativity. Or is it the one on the right?

int sum(int const& value1, int const& value2, int const& value3)
{
    return value1 + (value2 + value3);
}

This would be right associativity.

When we write this fold expression:

template<typename... Values>
auto sum(Values const&... values)
{
    return (values + ...);
}

It is right associative. It is equivalent to this:

int sum(int const& value1, int const& value2, int const& value3)
{
    return value1 + (value2 + value3);
}

We can also make the fold expression left associative by inverting the position of the variadic pack and the dot dot dot:

template<typename... Values>
auto sum(Values const&... values)
{
    return (... + values);
}

This creates a left-associative expression:

int sum(int const& value1, int const& value2, int const& value3)
{
    return (value1 + value2) + value3;
}

A way to remember it is that the associativity is on the same side as the dot dot dot.

An example where associativity matters

operator+ is the simplest operator we can think of, and in the above case with ints, left or right associative are rather theoretical considerations and lead to the same result.

To illustrate that associativity can matter, let’s take an example where left and right associativity don’t lead to the same result: operator-.

Let’s rewrite our function with operator-:

template<typename... Values>
auto f(Values const&... values)
{
    return (values - ...);
}

When we call it with f(1, 2, 3), the fold expression expands to 1 - (2 - 3), which is equal to 1 - (-1), which is equal to 2.

But if we write the dot dot dot on the left like this:

template<typename... Values>
auto f(Values const&... values)
{
    return (... - values);
}

Then when we call it with f(1, 2, 3), the fold expression expands to (1 - 2) - 3, which is equal to -1 - 3, which is equal to -4. Quite a different result.

How to deal with empty parameters pack

A template parameters pack can contain any number of parameters… including zero!

Let’s take our sum function again, for example the left-associative version:

template<typename... Values>
auto sum(Values const&... values)
{
    return (... + values);
}

Consider what happens if we call our sum function this way:

sum()

Then the compiler must return the result of not applying operator+ on anything. How does it do that?

It doesn’t. Instead it throws its compiler hands into the compiler air and outputs an error message such as this (here with gcc 9.2):

In instantiation of 'auto sum(const Values& ...) [with Values = {}]':
required from here
error: fold of empty expansion over operator+
return (values + ...);

But if you’re creating a sum function, you may want to it to work with any number of parameters (or maybe you don’t, and it’s your right as an API designer, but let’s assume that you’d rather it works with any number of parameters).

Then we need to define what the function should do in the case where it receives no input. If we really want our function to work with any type, then it is a difficult decision. To simplify it, let’s assume that we want our function to work with numeric types.

Then one way is to start the sum with a 0. Fold expressions allow us to do that by letting the 0 inside of the expression, inside of the parentheses:

template<typename... Values>
auto sum(Values const&... values)
{
    return (0 + ... + values);
}

Note that it is important to put the initial value inside of the fold expression. Indeed, if we put it outside, like this:

template<typename... Values>
auto sum(Values const&... values)
{
    return 0 + (... + values);
}

Then we’re back to the initial error message, because the fold expression still can’t be instantiated:

In instantiation of 'auto sum(const Values& ...) [with Values = {}]':
required from here
error: fold of empty expansion over operator+
return (values + ...);

How fold expressions can make your code more expressive

This is about all there is to know about fold expressions in C++, at least from the aspect of their definition.

Now that all this is clear, we need to see concrete examples where fold expressions can make your code more expressive. This is the topic of the next post. Stay tuned!

You will also like

Don't want to miss out ? Follow:   twitterlinkedinrss
Share this post!Facebooktwitterlinkedin