"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
– Marcin, Commented May 3, 2012 at 13:07
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
– Marcin, Commented May 3, 2012 at 13:10
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
– David Rodríguez - dribeas, Commented May 3, 2012 at 13:13
"“Deep” function currying in C++ using template metaprogramming" Dude, stop messing about and get back to what you are supposed to be doing. — Ben
– Ben, Commented May 3, 2012 at 15:47

vhallac · Accepted Answer · 2012-05-04 11:12:28Z

4

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.

edited May 4, 2012 at 11:12

answered May 3, 2012 at 21:47

vhallac

14.2k3 gold badges28 silver badges36 bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

isekaijin Over a year ago

Not quite. Despite its signature, your specialization effectively behaves as a curry< _Res( _Res2, _Args...) >. What you are passing to plus_axb_c.operator() is 12, not std::multiplies<int>().

vhallac Over a year ago

@EduardoLeón I felt that that was the case, but I couldn't figure out how we want to use the result. plus_axb_c(3)(4)(5)?

vhallac Over a year ago

How about something more complex, such as (arg1 -> arg2 -> tmp1) -> (arg3 -> arg4 -> tmp2) -> res?

isekaijin Over a year ago

plus_axb_c should not be passed std::plus<int>() at construction time. It should be passed a function that takes another function and an integer. Also, plus_axb_c.operator() should be passed a single integer, 5. The function you pass to plus_axb_c at construction time should internally pass 3 and 4 to the function it takes as parameter.

vhallac Over a year ago

@EduardoLeón Ah, I get it. So, essentially, I will need to implement a decurry method, and decurry the parameter arg in operator()(_Res2 arg). I am trying to make a working decurry implementation, so I cannot fix my answer yet. Feel free to link a working implementation. :)

|

Collectives™ on Stack Overflow

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

1 Answer 1

7 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

7 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related