Cfon Cfon - 2 months ago 25
C++ Question

C++11: lambda, currying

I have the following code. Can you explain to me how it works?

template<typename Function, typename... Arguments>
auto curry(Function func, Arguments... args) {
return [=](auto... rest) {
return func(args..., rest...);
};
}

int main() {
auto add = [](auto x, auto y) {
return x + y;
};
auto add4 = curry(add, 4);
std::cout << add4(3) << '\n'; //output: 7. (Ok)

}

Answer

First, you have to know what currying is. Basically, it means reducing a function with a certain number of parameters to create another function with some of the parameter's values fixed (it can also be called partial application)

I your exampled, the original function is add(x,y) which has two parameters x and y. You curry the function add by setting x to 4 and create the reduced function add4(y) such as

add4(y) = add(x,y) where x = 4

Now how is this achieved in your c++ code ? With the help of variadic templates, variadic functions and lambda functions.

Lambda functions are in c++ since C++11. In essence they are anonymous function created on the fly, which can be stored in a variable. You create add as a lambda in main() :

auto add = [](auto x, auto y) {
 return x + y;
};

One recognizes the lambda by the pattern [] (list-of-arguments) {function-body};

Note : the [] is not always empty, see "capturing variables" there, we'll get back to it later.

Now the curry function's purpose is to take one of these lambdas functions func and a certain number of values as arguments, and define a new function by assigning the values, in order, to the first arguments of func.

The "certain number of arguments" mechanism is permitted by the variadic template argument Arguments... args which permits to call the template with any number of types as template parameters (as long as they are known as compile time). So in our case, the passed argument is 4, so Arguments... args will be replaced by int, and the instance of curry will accept as parameters a lambda and an int.

If we look at the code of curry itself, we see that it is only a lambda function itself, (it is a variadic function, just like printf()) whose only purpose is to concatenate the arguments whose value is already fixed when instantiating the template(args...) and those whose value is passed as arguments to the curried function(rest...).

The [=] sign is a special capture for lambda function which allows to use all local variables in the function body (here it allows to use args).

So to wrap it up, here's what happening in your main function :

  1. You create a variable named add which contains a lambda function, taking two arguments and adding them.
  2. When you call curry(add,4) you instantiate the curry template.
    • The first template parameter Function is the type of add (a lambda taking two int and returning an int)
    • The second variadic parameters contains only one type : the type of 4, i.e. int

The instantiated curry function looks like this

curry( (int,int)->(int) func, int arg){
    return [=](auto... rest) {return func(arg, rest...);};
}

Note that you never see these types because of auto and template type deduction.

  1. You then call this instance with func = add and arg = 4

  2. You store the result of this instantiation in add4 which is now a lambda taking one parameter. You can then call add4 with 3 as argument (rest... is 3), which will then call add(4,3) and return 7.

Note that technically you could try to call add4 with more than one argument, since the curried function is a variadic function. The compiler will only fail when it figures out it doesn't have a place for these extra arguments when calling add (see it here)