"Deep" function currying in C++ using template metaprogramming

Question

I just came up with an (yet another!) implementation of function currying in C++ using template metaprogramming. (I am almost sure other implementations are better / more complete than mine, but I am doing this for learning purposes, a case in which I think reinventing the wheel is justified.)

My funcion currying implementation, test case included, is the following one:

#include <iostream>
#include <functional>

template <typename> class curry;

template <typename _Res>
class curry< _Res() >
{
  public:
    typedef std::function< _Res() > _Fun;
    typedef _Res _Ret;

  private:
    _Fun _fun;

  public:
    explicit curry (_Fun fun)
    : _fun(fun) { }

    operator _Ret ()
    { return _fun(); }
};

template <typename _Res, typename _Arg, typename... _Args>
class curry< _Res(_Arg, _Args...) >
{
  public:
    typedef std::function< _Res(_Arg, _Args...) > _Fun;
    typedef curry< _Res(_Args...) > _Ret;

  private:
    class apply
    {
      private:
        _Fun _fun;
        _Arg _arg;

      public:
        apply (_Fun fun, _Arg arg) 
        : _fun(fun), _arg(arg) { }

        _Res operator() (_Args... args)
        { return _fun(_arg, args...); }
    };

  private:
    _Fun _fun;

  public:
    explicit curry (_Fun fun)
    : _fun(fun) { }

    _Ret operator() (_Arg arg)
    { return _Ret(apply(_fun, arg)); }
};

int main ()
{
  auto plus_xy = curry<int(int,int)>(std::plus<int>());
  auto plus_2x = plus_xy(2);
  auto plus_24 = plus_2x(4);
  std::cout << plus_24 << std::endl;

  return 0;
}

This function currying implementation is "shallow", in the following sense: If the original std::function's signature is...

(arg1, arg2, arg3...) -> res

Then the curried function's signature is...

arg1 -> arg2 -> arg3 -> ... -> res

However, if any of the arguments or the return type themselves can be curried, they do not get curried. For example, if the original std::function's signature is...

(((arg1, arg2) -> tmp), arg3) -> res

Then the curried function's signature will be...

((arg1, arg2) -> tmp) -> arg3 -> res

Instead of...

(arg1 -> arg2 -> tmp) -> arg3 -> res

Which is what I want. So I would like to have a "deep" currying implementation. Does anyone know how I could write it?

@vhallac:

This is the kind of function that should be passed to the constructor of curry<int(int(int,int),int)>:

int test(std::function<int(int,int)> f, int x)
{ return f(3, 4) * x; }

Then one should be able to do the following:

auto func_xy = curry<int(int(int,int),int)>(test);
auto plus_xy = curry<int(int,int)>(std::plus<int>());
auto func_px = func_xy(plus_xy);
auto func_p5 = func_px(5);
std::cout << func_p5 << std::endl;

I think it might help everyone if you wrote out at the type level what such a transformation would look like. — Marcin
You show the "shallow" type transformation; if you write down the deep transformation, that will clarify what you mean (I think it's clear, you seem to think it's clear, but maybe we don't think it means the same thing), both for the reader, and for you. — Marcin
Side note: _Res (and all other identifiers that start with underscore capital letter) are reserved for the implementation, as identifiers starting with underscore and a lower case letter in the global namespace. You might want to refactor the names — David Rodríguez - dribeas
"“Deep” function currying in C++ using template metaprogramming" Dude, stop messing about and get back to what you are supposed to be doing. — Ben

vhallac vhallac · Accepted Answer · 2012-05-03T21:47:03

I have implemented a cheating version of a decurry class to demonstrate how you would go about implementing the specialization. The version is cheating, because it gets declared as a friend of curry<T>, and accesses the internal _fun to convert a curried version of a function back to original. It should be possible to write a generic one, but I didn't want to spend more time on it.

The decurry implementation is:

template <typename _Res, typename... _Args>
class decurry< curry<_Res(_Args...)> > {
public:
    typedef curry<_Res(_Args...)> _Curried;
    typedef typename curry<_Res(_Args...)>::_Fun _Raw;

    decurry(_Curried fn): _fn(fn) {}

    _Res operator() (_Args... rest) {
        return _fn._fun(rest...);
    }
private:
    _Curried _fn;
};

And it requires the line:

friend class decurry< curry<_Res(_Arg, _Args...)> >;

inside class curry< _Res(_Arg, _Args...) > to give our class access to curry<T>._fun.

Now, the specialization can be written as:

template <typename _Res, typename _Res2, typename... _Args2, typename... _Args>
class curry< _Res(_Res2(_Args2...), _Args...) >
{
public:
    typedef curry< _Res2(_Args2...) > _Arg;
    typedef std::function< _Res2(_Args2...) > _RawFun;
    typedef std::function< _Res(_RawFun, _Args...) > _Fun;
    typedef curry< _Res(_Args...) > _Ret;

private:
    class apply
    {
    private:
        _Fun _fun;
        _RawFun _arg;

    public:
        apply (_Fun fun, _RawFun arg)
            : _fun(fun), _arg(arg) { }

        _Res operator() (_Args... args)
        { return _fun(_arg, args...); }
    };

private:
    _Fun _fun;

public:
    explicit curry (_Fun fun)
        : _fun(fun) { }

    _Ret operator() (_Arg arg)
    { return _Ret(apply(_fun, decurry<_Arg>(arg))); }
};

The test code is a specified in the question:

int test(std::function<int(int,int)> f, int x)
{ return f(3, 4) * x; }

int main ()
{
    auto func_xy = curry<int(int(int,int),int)>(test);
    auto plus_xy = curry<int(int,int)>(std::plus<int>());
    auto func_px = func_xy(plus_xy);
    auto func_p5 = func_px(5);
    std::cout << func_p5 << std::endl;

    return 0;
}

The code output is on Ideone.com again.

"Deep" function currying in C++ using template metaprogramming

1 Answers