[Перевод] Currying and partial application in C++1417.01.2019 18:47

In this article I’m going to tell you about one of the currying options and partial application of the functions in C++ which is my personal favourite. I’m also going to show my own pilot implementation of this thing and explain the point of currying without complex mathematical formula, making it really simple for you. We’ll also see what’s under the hood of kari.hpp library which we’ll be using for currying functions. Anyway, there are lots of fascinating stuff inside, so welcome!

Currying

So, what is currying? I guess it’s one of those words you hear from Haskell programmers all the time (after monad, of course). Essentially, the definition of the term is pretty simple, so those readers who have already written on ML type languages or Haskell, or who knows what it means from elsewhere, feel free to skip this section.

Currying — is the technique of transforming a function that takes N arguments into one function, which takes a single argument and returns the function of the next argument, and it goes on and one until we return the last argument’s function, which is going to represent the overall result. I think it helps if I show you examples:

int sum2(int lhs, int rhs) {
  return lhs + rhs;
}

Here we have a binary addition function. And what if we want to turn it into single variable function? It’s actually very simple:

auto curried_sum2(int lhs) {
  return [=](int rhs) {
    return sum2(lhs, rhs);
  };
}

No, what did we do? We took a value based on a single argument called lambda that in turn takes the second argument and performs the addition itself. As the result, we can apply the curried function curried_sum2 to our arguments one by one:

// output: 42
std::cout << sum2(40, 2) << std::endl;
std::cout << curried_sum2(40)(2) << std::endl;

And that’s actually the whole point of currying operation. Of course, it’s possible to do it with functions of any arity — it’s going to work absolutely the same way. We will return a curried function of N-1 arguments every time we take the value from another argument:

auto sum3(int v1, int v2, int v3) {
  return v1 + v2 + v3;
}

auto curried_sum3(int v1) {
  return [=](int v2){
    return [=](int v3){
      return sum3(v1, v2, v3);
    };
  };
}

// output: 42
std::cout << sum3(38, 3, 1) << std::endl;
std::cout << curried_sum3(38)(3)(1) << std::endl;

Partial application

Partial application — is a way of calling functions of N arguments when they take only a part of the arguments and return another function of the remaining arguments.

In this regard it should be noted that in languages like Haskell this process works automatically, behind a programmer’s back. What we’re trying to do here is to perform it explicitly, i.e. to call our sum3 function like this: sum3(38,3)(1) or maybe like this: sum3(38)(3,1). On top of that, if one function returns another function that has been curried, it can be also called using the list of the first function’s arguments. Let’s see the example:

int boo(int v1, int v2) {
  return v1 + v2;
}

auto foo(int v1, int v2) {
  return kari::curry(boo, v1 + v2);
}

// output: 42
std::cout << kari::curry(foo)(38,3,1) << std::endl;
std::cout << kari::curry(foo)(38,3)(1) << std::endl;
std::cout << kari::curry(foo)(38)(3,1) << std::endl;

We actually have got a little ahead of ourselves here, showing an example of kari.hpp usage, so yes, it does that.

Setting the goals

Before we write something, it’s necessary (or desirable) to understand what we want to have in the end. And we want to have an opportunity to curry and partially apply any function that can be called in C++. Which are:

• lambdas (including generic ones)
• function objects (functors)
• functions of any arity (including templates)
• variadic functions
• methods of a class

Variadic functions can be curried by specifying an exact number of arguments we want to curry. Standard interaction with std: bind and its results are also desirable. And of course, we need an opportunity to apply multiple-variable functions and call nested functions so that it would seem like we’ve been working with one curried function.

And we must not forget about performance, too. We need to minimize computational costs of wrappers, transfer of arguments and their storage. It means we have to move instead of copying, store only what we really need, and return (with further removal) the data as fast as possible.

Author, you’ve been trying to invent std::bind one again!

Yes, and no. std::bind is undoubtedly a powerful and proven tool, and I don’t intend to write its murderer or alternative. Yes, it can be used for currying and explicit partial application (with specifying exactly what arguments we’re applying, and where, and how many). But it sure it not the most convenient approach, not to mention that it’s not always applicable since we have to know the arity of function and write specific bindings depending on that. For example:

int foo(int v1, int v2, int v3, int v4) {
  return v1 + v2 + v3 + v4;
}

// std::bind
auto c0 = std::bind(foo, _1, _2, _3, _4);
auto c1 = std::bind(c0, 15, _1, _2, _3);
auto c2 = std::bind(c1, 20, 2, _1);
auto rr = c2(5);
std::cout << rr << std::endl; // output: 42

// kari.hpp
auto c0 = kari::curry(foo);
auto c1 = c0(15);
auto c2 = c1(20, 2);
auto rr = c2(5);
std::cout << rr << std::endl; // output: 42

API

namespace kari {
  template < typename F, typename... Args >
  constexpr decltype(auto) curry(F&& f, Args&&... args) const;

  template < typename F, typename... Args >
  constexpr decltype(auto) curryV(F&& f, Args&&... args) const;

  template < std::size_t N, typename F, typename... Args >
  constexpr decltype(auto) curryN(F&& f, Args&&... args) const;

  template < typename F >
  struct is_curried;

  template < typename F >
  constexpr bool is_curried_v = is_curried::value;

  template < std::size_t N, typename F, typename... Args >
  struct curry_t {
    template < typename... As >
    constexpr decltype(auto) operator()(As&&... as) const;
  };
}

kari::curry(F&& f, Args&&... args)

Returns a function object of curry_t type (a curried function) with optional arguments args applied or with the result of application of the arguments to the given function f (is the function is nullary, or the arguments transferred were enough to call it).

If f parameter contains the function that has already been curried, it returns its copy with the arguments args applied.

kari::curryV(F&& f, Args&&... args)

Allows to curry functions with variable number of arguments. After that these functions can be called using () operator with no arguments. For example:

auto c0 = kari::curryV(std::printf, "%d + %d = %d");
auto c1 = c0(37, 5);
auto c2 = c1(42);
c2(); // output: 37 + 5 = 42

If f parameter contains a function that has already been curried, it returns its copy with altered type of application for variable number of arguments with the arguments args applied.

kari::curryN(F&& f, Args&&... args)

Allows to curry functions with variable number of arguments by specifying an exact number N of arguments we want to apply (except those given in args). For example:

char buffer[256] = {'\0'};
auto c = kari::curryN<3>(std::snprintf, buffer, 256, "%d + %d = %d");
c(37, 5, 42);
std::cout << buffer << std::endl;  // output: 37 + 5 = 42

If f parameter contains a function that has already been curried, it returns its copy with altered type of application for N arguments with the arguments args applied.

kari::is_curried, kari::is_curried_v

Some auxiliary structures for checking if a function has already been curried. For example:

const auto l = [](int v1, int v2){
  return v1 + v2;
};
const auto c = curry(l);

// output: is `l` curried? no
std::cout
  << "is `l` curried? "
  << (is_curried::value ? "yes" : "no")
  << std::endl;

// output: is `c` curried? yes
std::cout
  << "is `c` curried? "
  << (is_curried_v ? "yes" : "no")
  << std::endl;

kari::curry_t::operator()(As&&... as)

The operator allowing a full or partial application of a curried function. Returns the curried function of remaining arguments of the initial function F, or value of this function obtained by its application on the backlog of old arguments and new arguments as. For example:

int foo(int v1, int v2, int v3, int v4) {
  return v1 + v2 + v3 + v4;
}

auto c0 = kari::curry(foo);
auto c1 = c0(15, 20); // partial application
auto rr = c1(2, 5); // function call - foo(15,20,2,5)
std::cout << rr << std::endl; // output: 42

If you call a curried function with no arguments using curryV or curryN, it will be called if there are enough arguments. Otherwise, it will return a partially applied function. For example:

auto c0 = kari::curryV(std::printf, "%d + %d = %d");
auto c1 = c0(37, 5);
auto c2 = c1(42);

// force call variadic function std::printf
c2(); // output: 37 + 5 = 42

Details of implementation

When giving you details of implementation, I’m going to use C++17 in order to keep the text of the article short and avoid unnecessary explanations and piled SFINAE, as well as examples of implementations I had to add within the C++14 standard. All these you can find in the project repository, where you can also add it to your favourites:)

make_curry(F&& f, std::tuple&& args)

An auxiliary function that creates a function object curry_t or applies the given function f to the arguments args.

template < std::size_t N, typename F, typename... Args >
constexpr auto make_curry(F&& f, std::tuple&& args) {
  if constexpr ( N == 0 && std::is_invocable_v ) {
    return std::apply(std::forward(f), std::move(args));
  } else {
    return curry_t<
      N,
      std::decay_t,
      Args...
    >(std::forward(f), std::move(args));
  }
}

template < std::size_t N, typename F >
constexpr decltype(auto) make_curry(F&& f) {
  return make_curry(std::forward(f), std::make_tuple());
}

Now, there are two interesting things about this function:

• we apply it to the arguments only if it’s callable for these arguments and the application counter N is at zero
• if the function is not callable, we consider this call as partial application and create a function object curry_t containing the function and the arguments

struct curry_t

The function object supposed to store the backlog of arguments and the function we will call when applying it in the end. This object is what we’re going to call and apply partially.

template < std::size_t N, typename F, typename... Args >
struct curry_t {
  template < typename U >
  constexpr curry_t(U&& u, std::tuple&& args)
  : f_(std::forward(u))
  , args_(std::move(args)) {}
private:
  F f_;
  std::tuple args_;
};

template < std::size_t N, typename F, typename... Args >
struct curry_t {
  // 1
  constexpr decltype(auto) operator()() && {
    return detail::make_curry<0>(
      std::move(f_),
      std::move(args_));
  }

  // 2
  template < typename A >
  constexpr decltype(auto) operator()(A&& a) && {
    return detail::make_curry<(N > 0 ? N - 1 : 0)>(
      std::move(f_),
      std::tuple_cat(
        std::move(args_),
        std::make_tuple(std::forward(a))));
  }

  // 3
  template < typename A, typename... As >
  constexpr decltype(auto) operator()(A&& a, As&&... as) && {
    return std::move(*this)(std::forward(a))(std::forward(as)...);
  }

  // 4
  template < typename... As >
  constexpr decltype(auto) operator()(As&&... as) const & {
    auto self_copy = *this;
    return std::move(self_copy)(std::forward(as)...);
  }
}

using namespace kari::underscore;
std::vector v{1,2,3,4,5};
std::accumulate(v.begin(), v.end(), 0, _+_);        // result: 15
std::transform(v.begin(), v.end(), v.begin(), _*2); // v = 2, 3, 6, 8, 10
std::transform(v.begin(), v.end(), v.begin(), -_);  // v = -2,-3,-6,-8,-10

using namespace kari::underscore;

// 1
std::cout << (_*2) * (_+2) * 4 << std::endl; // output: 12

// 2
std::cout << 4 * (_*2) * (_+2) << std::endl; // output: 10

// (. (+2)) (*2) $ 10 == 24 // haskell analog
std::cout << (_*(_+2))(_*2) * 10 << std::endl; // output: 24

// ((+2) .) (*2) $ 10 == 22 // haskell analog
std::cout << ((_+2)*_)(_*2) * 10 << std::endl; // output: 22