Currying and Partial Application in C++14

Introduction

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 is 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 know 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 on 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 also be 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 is 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<F>::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<F>, kari::is_curried_v<F>

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<decltype(l)>::value ? "yes" : "no")
  << std::endl;

// output: is `c` curried? yes
std::cout
  << "is `c` curried? "
  << (is_curried_v<decltype(c)> ? "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...>&& 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...>&& args) {
  if constexpr ( N == 0 && std::is_invocable_v<F, Args...> ) {
    return std::apply(std::forward<F>(f), std::move(args));
  } else {
    return curry_t<
      N,
      std::decay_t<F>,
      Args...
    >(std::forward<F>(f), std::move(args));
  }
}

template < std::size_t N, typename F >
constexpr decltype(auto) make_curry(F&& f) {
  return make_curry<N>(std::forward<F>(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...>&& args)
  : f_(std::forward<U>(u))
  , args_(std::move(args)) {}
private:
  F f_;
  std::tuple<Args...> args_;
};

There are a number of reasons why we store the backlog of arguments args_ in std::tuple:

1. Situations with std::ref are handled automatically to store references when we need to, by default based on the value
2. Convenient application of a function according to its arguments (std::apply)
3. It's readymade, so you don't have to write it from scratch :)

We have store the object we call and the function f_ by its value, too, and be careful when choosing the type when creating one (I'm going to expand on this issue below), or moving, or copying it using universal reference in the constructor.

A template parameter N acts as an application counter for variadic functions.

curry_t::operator()(const As&...)

And, of course, the thing that makes it all work - the operator which calls the function object.

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>(a))));
  }

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

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

The calling operator has four functions overloaded.

1. A function with no parameters allowing to start applying the variadic function (created by curryV or curryN). Here, we decrement the application counter down to zero, making it clear that the function is ready to be applied, and then we give everything that's required for that to make_curry function.

2. A function of a single argument that decrements the application counter by 1 (if it's not at zero) and puts our new argument a in the backlog of arguments args_ and transfers all this to make_curry.

3. A variadic function that is actually a trick for partial application of various arguments. What it does is applies them recursively, one by one. Now, there are two reasons why they can't be applied all in once:

   • The application counter can get down to zero before there are no arguments left.
   • The function f_ can be called earlier and return another curried function, so all the next arguments will be intended for it.

4. The last function acts as a bridge between calling curry_t using lvalue and calling functions using rvalue.

The tags of ref-qualified functions make the whole process almost magical. To put it briefly, with their help, we get to know that an object was called using rvalue reference and we can just move the arguments instead of copying them in the end calling function make_curry. Otherwise, we'd have to copy the arguments in order to still have an opportunity to call this function again, making sure the arguments are still there.

Bonuses

Before proceeding to the conclusion, I would like to show you a couple of examples of the syntactic sugar they have in kari.hpp which can be qualified as bonuses.

Operator Sections

The programmers who've already worked with Haskell should be familiar with operator sections allowing to give a short description of the operators applied. For instance, structure (*2), generates a single-argument function, returning the result of multiplication of this argument by 2. So, what I wanted was to try writing something like that in C++. No sooner said than done!

using namespace kari::underscore;
std::vector<int> 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

Function Composition

And of course, I wouldn't be a complete wacko if I haven't tried to write a function composition. As the composition operator, I chose operator * as the closest (by the look of it) of all symbols available to the composition sign in maths. I used it to apply the resulting function for an argument, too. So, that's what I got:

using namespace kari::underscore;

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

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

1. composition of functions (*2) and (+2) is applied to 4. (4 + 2) * 2 = 12
2. function (*2) is applied to 4 and then we apply (+2) to the result. (4 * 2 + 2) = 10

The same way you can build quite complex compositions in pointfree style, but bear in mind only Haskell programmers will understand these. :)

// (. (+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

Conclusion

I think it was pretty clear before that there's no need to use these techniques in real projects. But still, I must mention that. After all, my goal was to prove myself and check the new C++ standard. Would I be able to do this? And would C++? Well, I guess, you just saw like we both have kind of done that. And I'm really grateful to all guys who read the whole thing.

History

• 17^th January, 2019: Initial version