c++ - How should I make function curry?

Question

In C++14, what is a good way to curry functions or function objects?

In particular, I have an overloaded function foo with some random number of overloads: some overloads may be found via ADL, others may be defined in a myriad of places.

I have a helper object:

static struct {
  template<class...Args>
  auto operator()(Args&&...args)const
  -> decltype(foo(std::forward<Args>(args)...))
    { return (foo(std::forward<Args>(args)...));}
} call_foo;

that lets me pass the overload set around as a single object.

If I wanted to curry foo, how should I do so?

As curry and partial function application are often used interchangeably, by curry I mean if foo(a,b,c,d) is a valid call, then curry(call_foo)(a)(b)(c)(d) must be a valid call.

Answer 1

Here is my current best attempt.

#include <iostream>
#include <utility>
#include <memory>

SFINAE utility helper class:

template<class T>struct voider{using type=void;};
template<class T>using void_t=typename voider<T>::type;

A traits class that tells you if Sig is a valid invokation -- ie, if std::result_of<Sig>::type is defined behavior. In some C++ implementations simply checking std::result_of is enough, but that isn't required by the standard:

template<class Sig,class=void>
struct is_invokable:std::false_type {};
template<class F, class... Ts>
struct is_invokable<
  F(Ts...),
  void_t<decltype(std::declval<F>()(std::declval<Ts>()...))>
>:std::true_type {
  using type=decltype(std::declval<F>()(std::declval<Ts>()...));
};
template<class Sig>
using invoke_result=typename is_invokable<Sig>::type;
template<class T> using type=T;

Curry helper is sort of a manual lambda. It captures a function and one argument. It isn't written as a lambda so we can enable proper rvalue forwarding when it is used in an rvalue context, which is important when currying:

template<class F, class T>
struct curry_helper {
  F f;
  T t;
  template<class...Args>
  invoke_result< type<F const&>(T const&, Args...) >
  operator()(Args&&...args)const&
  {
    return f(t, std::forward<Args>(args)...);
  }
  template<class...Args>
  invoke_result< type<F&>(T const&, Args...) >
  operator()(Args&&...args)&
  {
    return f(t, std::forward<Args>(args)...);
  }
  template<class...Args>
  invoke_result< type<F>(T const&, Args...) >
  operator()(Args&&...args)&&
  {
    return std::move(f)(std::move(t), std::forward<Args>(args)...);
  }
};

The meat and potatoes:

template<class F>
struct curry_t {
  F f;
  template<class Arg>
  using next_curry=curry_t< curry_helper<F, std::decay_t<Arg> >;
  // the non-terminating cases.  When the signature passed does not evaluate
  // we simply store the value in a curry_helper, and curry the result:
  template<class Arg,class=std::enable_if_t<!is_invokable<type<F const&>(Arg)>::value>>
  auto operator()(Arg&& arg)const&
  {
    return next_curry<Arg>{{ f, std::forward<Arg>(arg) }};
  }
  template<class Arg,class=std::enable_if_t<!is_invokable<type<F&>(Arg)>::value>>
  auto operator()(Arg&& arg)&
  {
    return next_curry<Arg>{{ f, std::forward<Arg>(arg) }};
  }
  template<class Arg,class=std::enable_if_t<!is_invokable<F(Arg)>::value>>
  auto operator()(Arg&& arg)&&
  {
    return next_curry<Arg>{{ std::move(f), std::forward<Arg>(arg) }};
  }
  // These are helper functions that make curry(blah)(a,b,c) somewhat of a shortcut for curry(blah)(a)(b)(c)
  // *if* the latter is valid, *and* it isn't just directly invoked.  Not quite, because this can *jump over*
  // terminating cases...
  template<class Arg,class...Args,class=std::enable_if_t<!is_invokable<type<F const&>(Arg,Args...)>::value>>
  auto operator()(Arg&& arg,Args&&...args)const&
  {
    return next_curry<Arg>{{ f, std::forward<Arg>(arg) }}(std::forward<Args>(args)...);
  }
  template<class Arg,class...Args,class=std::enable_if_t<!is_invokable<type<F&>(Arg,Args...)>::value>>
  auto operator()(Arg&& arg,Args&&...args)&
  {
    return next_curry<Arg>{{ f, std::forward<Arg>(arg) }}(std::forward<Args>(args)...);
  }
  template<class Arg,class...Args,class=std::enable_if_t<!is_invokable<F(Arg,Args...)>::value>>
  auto operator()(Arg&& arg,Args&&...args)&&
  {
    return next_curry<Arg>{{ std::move(f), std::forward<Arg>(arg) }}(std::forward<Args>(args)...);
  }

  // The terminating cases.  If we run into a case where the arguments would evaluate, this calls the underlying curried function:
  template<class... Args,class=std::enable_if_t<is_invokable<type<F const&>(Args...)>::value>>
  auto operator()(Args&&... args,...)const&
  {
    return f(std::forward<Args>(args)...);
  }
  template<class... Args,class=std::enable_if_t<is_invokable<type<F&>(Args...)>::value>>
  auto operator()(Args&&... args,...)&
  {
    return f(std::forward<Args>(args)...);
  }
  template<class... Args,class=std::enable_if_t<is_invokable<F(Args...)>::value>>
  auto operator()(Args&&... args,...)&&
  {
    return std::move(f)(std::forward<Args>(args)...);
  }
};

template<class F>
curry_t<typename std::decay<F>::type> curry( F&& f ) { return {std::forward<F>(f)}; }

The final function is humorously short.

Note that no type erasure is done. Also note that the theoretical hand-crafted solution can have far fewer moves, but I don't think I needlessly copy anywhere.

Here is a test function object:

static struct {
  double operator()(double x, int y, std::nullptr_t, std::nullptr_t)const{std::cout << "first
"; return x*y;}
  char operator()(char c, int x)const{std::cout << "second
"; return c+x;}
  void operator()(char const*s)const{std::cout << "hello " << s << "
";}
} foo;

And some test code to see how it works:

int main() {
  auto f = curry(foo);
  // testing the ability to "jump over" the second overload:
  std::cout << f(3.14,10,std::nullptr_t{})(std::nullptr_t{}) << "
";
  // Call the 3rd overload:
  f("world");
  // call the 2nd overload:
  auto x =  f('a',2);
  std::cout << x << "
";
  // again:
  x =  f('a')(2);
}

live example

The resulting code is more than a bit of a mess. Lots of methods had to be repeated 3 times to handle &, const& and && cases optimally. The SFINAE clauses are long and complex. I ended up using both variardic args and varargs, with the varargs there to ensure a non-important signature difference in the method (and lower priority I think, not that it matters, the SFINAE ensures only one overload is ever valid, except this qualifiers).

The result of curry(call_foo) is an object that can be called one argument at a time, or many arguments at a time. You can call it with 3 arguments, then 1, then 1, then 2, and it does mostly the right thing. No evidence is exposed telling you how many arguments it wants, other than just trying to feed it arguments and seeing if the call is valid. This is required to handle overloading cases.

A quirk of the multiple-argument case is that it won't partially pass the packet to one curry, and use the rest as arguments to the return value. I could change that relatively easily by changing:

    return curry_t< curry_helper<F, std::decay_t<Arg> >>{{ f, std::forward<Arg>(arg) }}(std::forward<Args>(args)...);

to

    return (*this)(std::forward<Arg>(arg))(std::forward<Args>(args)...);

and the other two similar ones. That would prevent the technique of "jumping over" an overload that would otherwise be valid. Thoughts? It would mean that curry(foo)(a,b,c) would be logically identical to curry(foo)(a)(b)(c) which seems elegant.

Thanks to @Casey whose answer inspired much of this.

---

Most recent revision. It makes (a,b,c) behave much like (a)(b)(c) unless it is call that works directly.

#include <type_traits>
#include <utility>

template<class...>
struct voider { using type = void; };
template<class...Ts>
using void_t = typename voider<Ts...>::type;

template<class T>
using decay_t = typename std::decay<T>::type;

template<class Sig,class=void>
struct is_invokable:std::false_type {};
template<class F, class... Ts>
struct is_invokable<
  F(Ts...),
  void_t<decltype(std::declval<F>()(std::declval<Ts>()...))>
>:std::true_type {};

#define RETURNS(...) decltype(__VA_ARGS__){return (__VA_ARGS__);}

template<class D>
class rvalue_invoke_support {
  D& self(){return *static_cast<D*>(this);}
  D const& self()const{return *static_cast<D const*>(this);}
public:
  template<class...Args>
  auto operator()(Args&&...args)&->
  RETURNS( invoke( this->self(), std::forward<Args>(args)... ) )

  template<class...Args>
  auto operator()(Args&&...args)const&->
  RETURNS( invoke( this->self(), std::forward<Args>(args)... ) )

  template<class...Args>
  auto operator()(Args&&...args)&&->
  RETURNS( invoke( std::move(this->self()), std::forward<Args>(args)... ) )

  template<class...Args>
  auto operator()(Args&&...args)const&&->
  RETURNS( invoke( std::move(this->self()), std::forward<Args>(args)... ) )
};

namespace curryDetails {
  // Curry helper is sort of a manual lambda.  It captures a function and one argument
  // It isn't written as a lambda so we can enable proper rvalue forwarding when it is
  // used in an rvalue context, which is important when currying:
  template<class F, class T>
  struct curry_helper: rvalue_invoke_support<curry_helper<F,T>> {
    F f;
    T t;

    template<class A, class B>
    curry_helper(A&& a, B&& b):f(std::forward<A>(a)), t(std::forward<B>(b)) {}

    template<class curry_helper, class...Args>
    friend auto invoke( curry_helper&& self, Args&&... args)->
    RETURNS( std::forward<curry_helper>(self).f( std::forward<curry_helper>(self).t, std::forward<Args>(args)... ) )
  };
}

namespace curryNS {
  // the rvalue-ref qualified function type of a curry_t:
  template<class curry>
  using function_type = decltype(std::declval<curry>().f);

  template <class> struct curry_t;

  // the next curry type if we chain given a new arg A0:
  template<class curry, class A0>
  using next_curry = curry_t<::curryDetails::curry_helper<decay_t<function_type<curry>>, decay_t<A0>>>;

  // 3 invoke_ overloads
  // The first is one argument when invoking f with A0 does not work:
  template<class curry, class A0>
  auto invoke_(std::false_type, curry&& self, A0&&a0 )->
  RETURNS(next_curry<curry, A0>{std::forward<curry>(self).f,std::forward<A0>(a0)})

  // This is the 2+ argument overload where invoking with the arguments does not work
  // invoke a chain of the top one:
  template<class curry, class A0, class A1, class... Args>
  auto invoke_(std::false_type, curry&& self, A0&&a0, A1&& a1, Args&&... args )->
  RETURNS(std::forward<curry>(self)(std::forward<A0>(a0))(std::forwa