Folding in C++ using Variadic Function Template

Template parameter pack was introduced in C++11. Today we will utilise it to write our

fold

function. To the ones who don't know what a fold function the expression

fold(add, 1, 2, 3, 4, 5)

, we will output

(1 +(2 + (3 + (4 + 5)))) = 15

(which is left fold). Similarly for

fold(mul, 1, 2, 3, 4, 5)

, we will output 120. More about it can be found here.

Let's begin with the code.

The small snippet below is actually our fold function in all its glory.

// Base Case - Return the only remaining element.
template<typename Func, typename T>
T fold(Func f, T v){
    return v;
}

// General Case - Apply function to current element
// and folded output of the previous elements.
template<typename Func, typename T, typename... Args>
T fold(Func f, T first, Args... args){
    return f(first,fold(f, args...));
}

We can call our fold function in the following manner.

// Sample function for testing.
template <typename T>
T add(T x, T y) { return x + y; }

int main(){
    fold(add<double>, 1, 2, 3);
}

What happens here is, when we call fold in main, the general case is selected by the compiler and it deduces the types for the argument.

Func

get the type

double (*)(double, double)

, while T is

int

and the

Args

parameter pack as termed by the standard is

{ int , int }

. We essentially peel of the first argument from the pack and call the binary function with it and evaluation of fold applied to the remainder of the pack. If you are comfortable with recursion you will easily comprehend what is happening. That we are sort of creating a expression tree similar to shown below.

So for every recursive function we need a base case to end on. In this case, when we are just left with the function and a single argument, we return the argument. This gets us the base value and allows our tree to fold compute the output.

To visually see the types we assumed are actually the ones deduced by the compiler lets try the code below.

#include <iostream>

// Base Case - Return the only remaining element.
template <typename Func, typename T>
T fold(Func f, T v)
{
    std::cout << "Base Function :" << __PRETTY_FUNCTION__ << "\n";
    return v;
}

// General Case - Apply function to current element
// and folded output of the previous elements.
template <typename Func, typename T, typename... Args>
T fold(Func f, T first, Args... args)
{
    std::cout << __PRETTY_FUNCTION__ << "\n";
    return f(first, fold(f, args...));
}

// Sample functions for testing.
template <typename T>
T add(T x, T y) { return x + y; }

int main()
{
    fold(add<double>, 1, 2, 3);
}

Compiling and executing this code with a g++ compiler will give you.

T fold(Func, T, Args ...) [with Func = double (*)(double, double); T = int; Args = {int, int}]
T fold(Func, T, Args ...) [with Func = double (*)(double, double); T = int; Args = {int}]
Base Function :T fold(Func, T) [with Func = double (*)(double, double); T = int]

This is what we expected it to be. This is a sort of the representation of our tree.

Tip: With

constexpr

keyword at the correct places, we can easily make the compiler to compute the value at compile time if we know the arguments at compile time.