To curry or not to curry

[laedus]

Hello,

Has somebody already implemented these functions ?

template <typename X, typename A, typename B>
function<function<B(A)>(X)> curryfy (function<B(X,A)> f);

template <typename X, typename A, typename B>
function<B(X,A)> uncurryfy (function<function<B(A)>(X)> fbar);

where fbar(x)(a) = f(x,a)

Thanks in advance and best regards.

Laedus

[jonnin]

some context?

[laedus]

The idea is to have an interpretation of C++ in the theory of category.

The classes become objects, the functions become arrows, the templates lead to functors.

In this theory exists an exponential B^A we can get as function <B(A)>, and a product A x B well defined a user defined functor Prod as template<typename A, typename B> class Prod{A a; B b;}.

The Curry isomorphism is given by the two functions sopra.

A idea is to use the lambda [] possibility of C++, but I don't know how to us it in a function implementation. The problem is related to the pointer-to-member saga ...

[mbozzi]

Yes, it's been done many times.

Here's one (quite naive) C++17 implementation. It's possible earlier, it's just more complicated and longer.

#include <tuple> 
#include <type_traits>
#include <cassert>

namespace detail {
  template < typename Fn, typename Args, std::size_t... Is >
  constexpr auto
  partially_apply_impl(Fn fn, Args args,
                       std::index_sequence< Is... >) 
  {
    return [fn{std::move(fn)}, args] (auto... rest)
    {
      return fn(std::get<Is>(args)..., rest...);
    };
  }
}

template < typename Fn, typename Args >
constexpr auto partially_apply(Fn fn, Args args) {
  return detail::partially_apply_impl(
      fn, args,
      std::make_index_sequence< std::tuple_size<
          std::remove_reference_t< std::remove_cv_t< Args > > >::value >());
}

template < int N >
struct curry_t 
{
  template < typename Fn >
  constexpr auto
  operator()(Fn fn) const {
    return [fn](auto... args) {
      constexpr int remaining_free_variables =
          N - static_cast< int >(sizeof...(args));

      if constexpr (remaining_free_variables > 0)
        return curry_t< remaining_free_variables >{}(
            partially_apply(fn, std::make_tuple(args...)));
      else
        return fn(args...);
    };
  }
};

template < int N > inline constexpr curry_t< N > curry{};

struct equal_fn
{
  template <typename First, typename Last>
  constexpr auto operator()(First first, Last last) const
  {
    return first == last;
  }
};

inline constexpr auto equal = curry<2>(equal_fn{});


int main()
{
    assert(equal(1)(1));
    assert(equal(1)()(1));
    assert(equal(1, 1));
    assert(equal()(1, 1));

    assert(! equal(1)(2));
    assert(! equal(1)()(2));
    assert(! equal(1, 2));
    assert(! equal()(1, 2));
}

Live demo:
http://coliru.stacked-crooked.com/a/2fa558108be80821

It's pretty simple to write an uncurry function in terms of partially_apply(). But one has to write function objects, not functions, because functions are not first-class in C++.

[laedus]

Here is an implementation using the lambda operator

template <typename X, typename A, typename B>
function<function<B(A)>(X)> curryfy (function<B(X,A)> f) {
  return [f] (X x) {return  [f, x] (A a) { return f (x, a);};};
};

template <typename X, typename A, typename B>
function<B(X,A)> uncurryfy (function<function<B(A)>(X)> fbar) {
   return [fbar] (X x, A a) {return fbar(x)(a);};
};

Who says better ?

[mbozzi]

Who says better ?

The implementations are not equivalent.

The first approach above curries functions of any finite arity, and allows the user to call the result with any number of arguments at a time. There are two major usability benefits. Firstly, instead of curryfy(curryfy(curryfy(f))) it's curry<4>(f).

Secondly, it makes uncurry less necessary by removing the distinction between curry(f) and f (there is no such distinction in functional languages).

For example, a library that provides auto curried_equal = currify(equal_fn{}) and equal_fn{} equal forces the user to distinguish equal(a, b) from curried_equal(a)(b), whereas a library that provides constexpr auto equal = curry<2>(equal_fn{}) lets the user say both equal(a, b) and equal(a)(b), both behave as expected.

The former approach produces functions that are often usable in constant expressions, and is very slightly less general because it avoids std::function.

[laedus]

Thanks for you answer.

I will examine your code more carefully to understand it.

My idea was to use the simplest way - pure C++ vanilla - to implement these functions.

With multiple arguments, it is possible to pass a class with multiple members (a product), a t-uple or a vector.
Of course, in this case, it will not be possible to isolate groups of variables !

[mbozzi]

I remembered that C++17 provides std::apply, so here's a version of partially_apply that looks simpler:

template <typename Fn, typename Args>
constexpr auto partially_apply(Fn fn, Args args) {
  return [fn, args](auto... rest) {
    return std::apply(fn, std::tuple_cat(args, std::make_tuple(rest...)));
  };
}

http://coliru.stacked-crooked.com/a/fe7557095415c114