Before you go, check out these stories!

0
Hackernoon logoFolding in C++ using Variadic Function Template by@SoulCollector

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.

Tags

The Noonification banner

Subscribe to get your daily round-up of top tech stories!