Composition, currying, and partial function application

One advantage of Lambdas is you can compose two functions together to create a composition of functions as you do in mathematics (read about function composition in the context of mathematics and functional programming  using favorite search engine). The following program demonstrates the idea. This is a toy implementation and writing a general-purpose implementation is beyond the scope of this chapter:

//------------ Compose.cpp
//----- g++ -std=c++1z Compose.cpp
#include <iostream>
using namespace std;
//---------- base case compile time recursion
//---------- stops here
template <typename F, typename G>
auto Compose(F&& f, G&& g)
{ return [=](auto x) { return f(g(x)); };}
//----- Performs compile time recursion based
//----- on number of parameters
template <typename F, typename... R>
auto Compose(F&& f, R&&... r){
    return [=](auto x) { return f(Compose(r...)(x)); };
}

Compose is a variadic template function and the compiler generates code by recursively expanding the Compose arguments until all the arguments are processed. In the preceding code, we have used [=] to indicate to the compiler that we should capture all variables referenced in the body of the Lambda by value. You can study more about Closure and Variable Capture in the context of functional programming. The C++ language gives flexibility to Capture variables by value (as well as using [&]) or by specifying variables to be captured explicitly (such as [&var]).

The functional programming paradigm is based on a mathematical formalism called Lambda calculus invented by Alonzo Church, an American mathematician. The Lambda calculus supports only unary functions and currying is a technique that breaks a multiple argument function into a series of function evaluations that take one argument at a time.

Using Lambdas and writing functions in a specific manner, we can simulate currying in C++:

auto CurriedAdd3(int x) {
    return [x](int y) { //capture x
        return [x, y](int z){ return x + y + z; };
    };
};

The partial function application involves the conversion of functions with multiple arguments into a fixed number of arguments. If the fixed number of arguments is less than the arity (parameter count) of the function, a new function will be returned that expects the rest of the parameters. When all parameters are received, the function will be invoked. We can treat the partial application as some form of memorization where parameters are cached until we receive all of them to invoke them.

In the following code snippets, we have used  constructs like template parameter pack and variadic templates. A template parameter pack is a template parameter that accepts zero or more template arguments (non-types, types, or templates). A function parameter pack is a function parameter that accepts zero or more function arguments. A template with at least one parameter pack is called a variadic template. A good idea about parameter pack and variadic templates is necessary for understanding sizeof...  constructs.

template <typename... Ts>
auto PartialFunctionAdd3(Ts... xs) {
    //---- http://en.cppreference.com/w/cpp/language/parameter_pack
    //---- http://en.cppreference.com/w/cpp/language/sizeof...
    static_assert(sizeof...(xs) <= 3);
    if constexpr (sizeof...(xs) == 3){
        // Base case: evaluate and return the sum.
        return (0 + ... + xs);
    }
    else{
        // Recursive case: bind `xs...` and return another
        return [xs...](auto... ys){
            return PartialFunctionAdd3(xs..., ys...);
        };
    }
}
int main() {
    // ------------- Compose two functions together
    //----https://en.wikipedia.org/wiki/Function_composition
    auto val = Compose(
        [](int const a) {return std::to_string(a); },
        [](int const a) {return a * a; })(4); // val = "16"
    cout << val << std::endl; //should print 16
    // ----------------- Invoke the Curried function
    auto p = CurriedAdd3(4)(5)(6);
    cout << p << endl;
    //-------------- Compose a set of function together
    auto func = Compose(
        [](int const n) {return std::to_string(n); },
        [](int const n) {return n * n; },
        [](int const n) {return n + n; },
        [](int const n) {return std::abs(n); });
    cout << func(5) << endl;
    //----------- Invoke Partial Functions giving different arguments
    PartialFunctionAdd3(1, 2, 3);
    PartialFunctionAdd3(1, 2)(3);
    PartialFunctionAdd3(1)(2)(3);
}