How can currying be done in C++?

Question

What is currying?

How can currying be done in C++?

Please Explain binders in STL container?

Answer 1

1. What is currying?

Currying simply means a transformation of a function of several arguments to a function of a single argument. This is most easily illustrated using an example:

Take a function f that accepts three arguments:

int f(int a,std::string b,float c) {     // do something with a, b, and c     return 0; } 

If we want to call f, we have to provide all of its arguments f(1,"some string",19.7f).

Then a curried version of f, let's call it curried_f=curry(f) only expects a single argument, that corresponds to the first argument of f, namely the argument a. Additionally, f(1,"some string",19.7f) can also be written using the curried version as curried_f(1)("some string")(19.7f). The return value of curried_f(1) on the other hand is just another function, that handles the next argument of f. In the end, we end up with a function or callable curried_f that fulfills the following equality:

curried_f(first_arg)(second_arg)...(last_arg) == f(first_arg,second_arg,...,last_arg). 

2. How can currying be achieved in C++?

The following is a little bit more complicated, but works very well for me (using c++11)... It also allows currying of arbitrary degree like so: auto curried=curry(f)(arg1)(arg2)(arg3) and later auto result=curried(arg4)(arg5). Here it goes:

#include <functional>  namespace _dtl {      template <typename FUNCTION> struct     _curry;      // specialization for functions with a single argument     template <typename R,typename T> struct     _curry<std::function<R(T)>> {         using         type = std::function<R(T)>;                  const type         result;                  _curry(type fun) : result(fun) {}              };      // recursive specialization for functions with more arguments     template <typename R,typename T,typename...Ts> struct     _curry<std::function<R(T,Ts...)>> {         using         remaining_type = typename _curry<std::function<R(Ts...)> >::type;                  using         type = std::function<remaining_type(T)>;                  const type         result;                  _curry(std::function<R(T,Ts...)> fun)         : result (             [=](const T& t) {                 return _curry<std::function<R(Ts...)>>(                     [=](const Ts&...ts){                          return fun(t, ts...);                      }                 ).result;             }         ) {}     }; }  template <typename R,typename...Ts> auto curry(const std::function<R(Ts...)> fun) -> typename _dtl::_curry<std::function<R(Ts...)>>::type {     return _dtl::_curry<std::function<R(Ts...)>>(fun).result; }  template <typename R,typename...Ts> auto curry(R(* const fun)(Ts...)) -> typename _dtl::_curry<std::function<R(Ts...)>>::type {     return _dtl::_curry<std::function<R(Ts...)>>(fun).result; }  #include <iostream>  void  f(std::string a,std::string b,std::string c) {     std::cout << a << b << c; }  int  main() {     curry(f)("Hello ")("functional ")("world!");     return 0; } 

View output

OK, as Samer commented, I should add some explanations as to how this works. The actual implementation is done in the _dtl::_curry, while the template functions curry are only convenience wrappers. The implementation is recursive over the arguments of the std::function template argument FUNCTION.

For a function with only a single argument, the result is identical to the original function.

        _curry(std::function<R(T,Ts...)> fun)         : result (             [=](const T& t) {                 return _curry<std::function<R(Ts...)>>(                     [=](const Ts&...ts){                          return fun(t, ts...);                      }                 ).result;             }         ) {} 

Here the tricky thing: For a function with more arguments, we return a lambda whose argument is bound to the first argument to the call to fun. Finally, the remaining currying for the remaining N-1 arguments is delegated to the implementation of _curry<Ts...> with one less template argument.

Update for c++14 / 17:

A new idea to approach the problem of currying just came to me... With the introduction of if constexpr into c++17 (and with the help of void_t to determine if a function is fully curried), things seem to get a lot easier:

template< class, class = std::void_t<> > struct  needs_unapply : std::true_type { };   template< class T > struct  needs_unapply<T, std::void_t<decltype(std::declval<T>()())>> : std::false_type { };  template <typename F> auto curry(F&& f) {   /// Check if f() is a valid function call. If not we need    /// to curry at least one argument:   if constexpr (needs_unapply<decltype(f)>::value) {        return [=](auto&& x) {             return curry(                 [=](auto&&...xs) -> decltype(f(x,xs...)) {                     return f(x,xs...);                 }             );         };       }   else {       /// If 'f()' is a valid call, just call it, we are done.     return f();   } }  int  main() {   auto f = [](auto a, auto b, auto c, auto d) {     return a  * b * c * d;   };      return curry(f)(1)(2)(3)(4); } 

See code in action on here. With a similar approach, here is how to curry functions with arbitrary number of arguments.

The same idea seems to work out also in C++14, if we exchange the constexpr if with a template selection depending on the test needs_unapply<decltype(f)>::value:

template <typename F> auto curry(F&& f);  template <bool> struct curry_on;  template <> struct curry_on<false> {     template <typename F> static auto     apply(F&& f) {         return f();     } };  template <> struct curry_on<true> {     template <typename F> static auto      apply(F&& f) {         return [=](auto&& x) {             return curry(                 [=](auto&&...xs) -> decltype(f(x,xs...)) {                     return f(x,xs...);                 }             );         };     } };  template <typename F> auto curry(F&& f) {     return curry_on<needs_unapply<decltype(f)>::value>::template apply(f); } 

Answer 2

In short, currying takes a function f(x, y) and given a fixed Y, gives a new function g(x) where

g(x) == f(x, Y) 

This new function may be called in situations where only one argument is supplied, and passes the call on to the original f function with the fixed Y argument.

The binders in the STL allow you to do this for C++ functions. For example:

#include <functional> #include <iostream> #include <vector>  using namespace std;  // declare a binary function object class adder: public binary_function<int, int, int> { public:     int operator()(int x, int y) const     {         return x + y;     } };  int main() {     // initialise some sample data     vector<int> a, b;     a.push_back(1);     a.push_back(2);     a.push_back(3);      // here we declare a function object f and try it out     adder f;     cout << "f(2, 3) = " << f(2, 3) << endl;      // transform() expects a function with one argument, so we use     // bind2nd to make a new function based on f, that takes one     // argument and adds 5 to it     transform(a.begin(), a.end(), back_inserter(b), bind2nd(f, 5));      // output b to see what we got     cout << "b = [" << endl;     for (vector<int>::iterator i = b.begin(); i != b.end(); ++i) {         cout << "  " << *i << endl;     }     cout << "]" << endl;      return 0; }