如何在C++中完成currying？

Question

什么是currying？

如何在C++中完成currying？

请解释STL容器中的粘合剂？

Answer 1

1.什么是currying？

Currying只是意味着将几个参数的函数转换为单个参数的函数.使用示例可以很容易地说明这一点:

采用一个f接受三个参数的函数:

int
f(int a,std::string b,float c)
{
    // do something with a, b, and c
    return 0;
}

如果我们想要打电话f,我们必须提供它的所有论据f(1,"some string",19.7f).

那么一个curried版本f,让我们称curried_f=curry(f)它只需要一个参数,它对应于第一个参数f,即参数a.另外,f(1,"some string",19.7f)也可以使用curried版本编写curried_f(1)("some string")(19.7f).curried_f(1)另一方面,返回值只是另一个函数,它处理下一个参数f.最后,我们最终得到一个curried_f满足以下相等性的函数或可调用函数:

curried_f(first_arg)(second_arg)...(last_arg) == f(first_arg,second_arg,...,last_arg).

2.如何在C++中实现currying？

以下是有点复杂,但对我来说非常好(使用c ++ 11)...它也允许任意程度的卷曲,如此:auto curried=curry(f)(arg1)(arg2)(arg3)以及之后auto result=curried(arg4)(arg5).在这里:

#include <functional>

namespace _dtl {

    template <typename FUNCTION> struct
    _curry;

    // specialization for functions with a single argument
    template <typename R,typename T> struct
    _curry<std::function<R(T)>> {
        using
        type = std::function<R(T)>;

        const type
        result;

        _curry(type fun) : result(fun) {}

    };

    // recursive specialization for functions with more arguments
    template <typename R,typename T,typename...Ts> struct
    _curry<std::function<R(T,Ts...)>> {
        using
        remaining_type = typename _curry<std::function<R(Ts...)> >::type;

        using
        type = std::function<remaining_type(T)>;

        const type
        result;

        _curry(std::function<R(T,Ts...)> fun)
        : result (
            [=](const T& t) {
                return _curry<std::function<R(Ts...)>>(
                    [=](const Ts&...ts){ 
                        return fun(t, ts...); 
                    }
                ).result;
            }
        ) {}
    };
}

template <typename R,typename...Ts> auto
curry(const std::function<R(Ts...)> fun)
-> typename _dtl::_curry<std::function<R(Ts...)>>::type
{
    return _dtl::_curry<std::function<R(Ts...)>>(fun).result;
}

template <typename R,typename...Ts> auto
curry(R(* const fun)(Ts...))
-> typename _dtl::_curry<std::function<R(Ts...)>>::type
{
    return _dtl::_curry<std::function<R(Ts...)>>(fun).result;
}

#include <iostream>

void 
f(std::string a,std::string b,std::string c)
{
    std::cout << a << b << c;
}

int 
main() {
    curry(f)("Hello ")("functional ")("world!");
    return 0;
}

查看输出

好吧,正如Samer评论的那样,我应该补充一些关于它是如何工作的解释.实际的实现是在_dtl::_curry,而模板函数curry只是方便的包装器.该实现是对std::function模板参数的参数的递归FUNCTION.

对于只有一个参数的函数,结果与原始函数相同.

        _curry(std::function<R(T,Ts...)> fun)
        : result (
            [=](const T& t) {
                return _curry<std::function<R(Ts...)>>(
                    [=](const Ts&...ts){ 
                        return fun(t, ts...); 
                    }
                ).result;
            }
        ) {}

这里有一个棘手的问题:对于具有更多参数的函数,我们返回一个lambda,其参数绑定到调用的第一个参数fun.最后,剩下的N-1参数的剩余currying 被委托给_curry<Ts...>一个较少的模板参数的实现.

更新c ++ 14/17:

一个解决currying问题的新想法刚刚来到我身边......随着if constexprc ++ 17 的引入(并且在void_t确定一个函数是否完全通过的帮助下),事情似乎变得更加容易:

template< class, class = std::void_t<> > struct 
needs_unapply : std::true_type { };

template< class T > struct 
needs_unapply<T, std::void_t<decltype(std::declval<T>()())>> : std::false_type { };

template <typename F> auto
curry(F&& f) {
  /// Check if f() is a valid function call. If not we need 
  /// to curry at least one argument:
  if constexpr (needs_unapply<decltype(f)>::value) {
       return [=](auto&& x) {
            return curry(
                [=](auto&&...xs) -> decltype(f(x,xs...)) {
                    return f(x,xs...);
                }
            );
        };    
  }
  else {  
    /// If 'f()' is a valid call, just call it, we are done.
    return f();
  }
}

int 
main()
{
  auto f = [](auto a, auto b, auto c, auto d) {
    return a  * b * c * d;
  };

  return curry(f)(1)(2)(3)(4);
}

请参阅此处的代码.使用类似的方法,这里是如何使用任意数量的参数来curry函数.

如果我们constexpr if根据测试交换模板选择,那么同样的想法在C++ 14中似乎也有用needs_unapply<decltype(f)>::value:

template <typename F> auto
curry(F&& f);

template <bool> struct
curry_on;

template <> struct
curry_on<false> {
    template <typename F> static auto
    apply(F&& f) {
        return f();
    }
};

template <> struct
curry_on<true> {
    template <typename F> static auto 
    apply(F&& f) {
        return [=](auto&& x) {
            return curry(
                [=](auto&&...xs) -> decltype(f(x,xs...)) {
                    return f(x,xs...);
                }
            );
        };
    }
};

template <typename F> auto
curry(F&& f) {
    return curry_on<needs_unapply<decltype(f)>::value>::template apply(f);
}

Answer 2

总之,钻营接受一个函数f(x, y)和给出一个固定的Y,赋予了新的功能g(x),其中

g(x) == f(x, Y)

可以在仅提供一个参数的情况下调用此新函数,并f使用fixed Y参数将调用传递给原始函数.

STL中的绑定器允许您为C++函数执行此操作.例如:

#include <functional>
#include <iostream>
#include <vector>

using namespace std;

// declare a binary function object
class adder: public binary_function<int, int, int> {
public:
    int operator()(int x, int y) const
    {
        return x + y;
    }
};

int main()
{
    // initialise some sample data
    vector<int> a, b;
    a.push_back(1);
    a.push_back(2);
    a.push_back(3);

    // here we declare a function object f and try it out
    adder f;
    cout << "f(2, 3) = " << f(2, 3) << endl;

    // transform() expects a function with one argument, so we use
    // bind2nd to make a new function based on f, that takes one
    // argument and adds 5 to it
    transform(a.begin(), a.end(), back_inserter(b), bind2nd(f, 5));

    // output b to see what we got
    cout << "b = [" << endl;
    for (vector<int>::iterator i = b.begin(); i != b.end(); ++i) {
        cout << "  " << *i << endl;
    }
    cout << "]" << endl;

    return 0;
}

Answer 3

使用tr1简化Gregg的示例:

#include <functional> 
using namespace std;
using namespace std::tr1;
using namespace std::tr1::placeholders;

int f(int, int);
..
int main(){
    function<int(int)> g     = bind(f, _1, 5); // g(x) == f(x, 5)
    function<int(int)> h     = bind(f, 2, _1); // h(x) == f(2, x)
    function<int(int,int)> j = bind(g, _2);    // j(x,y) == g(y)
}

Tr1功能组件允许您在C++中编写丰富的功能样式代码.同样,C++ 0x也允许内联lambda函数执行此操作:

int f(int, int);
..
int main(){
    auto g = [](int x){ return f(x,5); };      // g(x) == f(x, 5)
    auto h = [](int x){ return f(2,x); };      // h(x) == f(2, x)
    auto j = [](int x, int y){ return g(y); }; // j(x,y) == g(y)
}

虽然C++没有提供一些面向功能的编程语言执行的丰富的副作用分析,但const分析和C++ 0x lambda语法可以帮助:

struct foo{
    int x;
    int operator()(int y) const {
        x = 42; // error!  const function can't modify members
    }
};
..
int main(){
    int x;
    auto f = [](int y){ x = 42; }; // error! lambdas don't capture by default.
}

希望有所帮助.

Answer 4

看看Boost.Bind,它使Greg显示的过程更加通用:

transform(a.begin(), a.end(), back_inserter(b), bind(f, _1, 5));

此结合5到f的第二个参数.

值得注意的是,这不是 currying(相反,它是部分应用程序).但是,在一般情况下使用currying在C++中很难(实际上,它最近才成为可能)并且经常使用部分应用程序.

Answer 5

如果您使用的是C++ 14,那么非常简单:

template<typename Function, typename... Arguments>
auto curry(Function function, Arguments... args) {
    return [=](auto... rest) {
        return function(args..., rest...);
    }
}

然后你可以像这样使用它:

auto add = [](auto x, auto y) { return x + y; }

// curry 4 into add
auto add4 = curry(add, 4);

add4(6); // 10

Answer 6

其他答案很好地解释了粘合剂,所以我不会在这里重复这一部分.我将仅演示如何在C++ 0x中使用lambdas进行currying和部分应用程序.

代码示例:(注释中的说明)

#include <iostream>
#include <functional>

using namespace std;

const function<int(int, int)> & simple_add = 
  [](int a, int b) -> int {
    return a + b;
  };

const function<function<int(int)>(int)> & curried_add = 
  [](int a) -> function<int(int)> {
    return [a](int b) -> int {
      return a + b;
    };
  };

int main() {
  // Demonstrating simple_add
  cout << simple_add(4, 5) << endl; // prints 9

  // Demonstrating curried_add
  cout << curried_add(4)(5) << endl; // prints 9

  // Create a partially applied function from curried_add
  const auto & add_4 = curried_add(4);
  cout << add_4(5) << endl; // prints 9
}

Answer 7

这里有一些很好的答案。我想我会添加自己的，因为尝试这个概念很有趣。

部分函数应用：仅将函数与其部分参数“绑定”的过程，推迟其余部分稍后填充。结果是另一个参数更少的函数。

柯里化（Currying）：是一种特殊形式的偏函数应用，一次只能“绑定”一个参数。结果是另一个函数的参数少了 1 个。

我将要展示的代码是部分函数应用程序，从中可以进行柯里化，但不是唯一的可能性。与上述柯里化实现相比，它提供了一些好处（主要是因为它是部分函数应用而不是柯里化，呵呵）。

• 应用于空函数：

  auto sum0 = [](){return 0;};
  std::cout << partial_apply(sum0)() << std::endl;
  

• 一次应用多个参数：

  auto sum10 = [](int a, int b, int c, int d, int e, int f, int g, int h, int i, int j){return a+b+c+d+e+f+g+h+i+j;};
  std::cout << partial_apply(sum10)(1)(1,1)(1,1,1)(1,1,1,1) << std::endl; // 10
  

• constexpr支持允许编译时static_assert：

  static_assert(partial_apply(sum0)() == 0);
  

• 如果您不小心提供太多参数，则会出现有用的错误消息：

  auto sum1 = [](int x){ return x;};
  partial_apply(sum1)(1)(1);
  

  错误：static_assert 失败“尝试应用太多参数！”

上面的其他答案返回绑定参数的 lambda，然后返回更多 lambda。这种方法将基本功能包装到可调用对象中。的定义允许operator()调用内部 lambda。可变参数模板允许我们检查是否有人走得太远，并且函数调用结果类型的隐式转换函数允许我们打印结果或将对象与基元进行比较。

代码：

namespace detail{
template<class F>
using is_zero_callable = decltype(std::declval<F>()());

template<class F>
constexpr bool is_zero_callable_v = std::experimental::is_detected_v<is_zero_callable, F>;
}

template<class F>
struct partial_apply_t
{
    template<class... Args>
    constexpr auto operator()(Args... args)
    {
        static_assert(sizeof...(args) == 0 || !is_zero_callable, "Attempting to apply too many arguments!");
        auto bind_some = [=](auto... rest) -> decltype(myFun(args..., rest...))
        {
           return myFun(args..., rest...);
        };
        using bind_t = decltype(bind_some);

        return partial_apply_t<bind_t>{bind_some};
    }
    explicit constexpr partial_apply_t(F fun) : myFun(fun){}

    constexpr operator auto()
    {
        if constexpr (is_zero_callable)
            return myFun();
        else
            return *this; // a callable
    }
    static constexpr bool is_zero_callable = detail::is_zero_callable_v<F>;
    F myFun;
};

现场演示

还有一些注意事项：

• 我选择使用is_Detected主要是为了享受和练习；它的作用与这里的正常类型特征相同。
• 出于性能原因，肯定需要做更多工作来支持完美转发
• 代码是 C++17，因为它需要C++17 中的constexprlambda 支持
  • 而且似乎 GCC 7.0.1 还没有完全实现，所以我使用了 Clang 5.0.0

一些测试：

auto sum0 = [](){return 0;};
auto sum1 = [](int x){ return x;};
auto sum2 = [](int x, int y){ return x + y;};
auto sum3 = [](int x, int y, int z){ return x + y + z; };
auto sum10 = [](int a, int b, int c, int d, int e, int f, int g, int h, int i, int j){return a+b+c+d+e+f+g+h+i+j;};

std::cout << partial_apply(sum0)() << std::endl; //0
static_assert(partial_apply(sum0)() == 0, "sum0 should return 0");
std::cout << partial_apply(sum1)(1) << std::endl; // 1
std::cout << partial_apply(sum2)(1)(1) << std::endl; // 2
std::cout << partial_apply(sum3)(1)(1)(1) << std::endl; // 3
static_assert(partial_apply(sum3)(1)(1)(1) == 3, "sum3 should return 3");
std::cout << partial_apply(sum10)(1)(1,1)(1,1,1)(1,1,1,1) << std::endl; // 10
//partial_apply(sum1)(1)(1); // fails static assert
auto partiallyApplied = partial_apply(sum3)(1)(1);
std::function<int(int)> finish_applying = partiallyApplied;
std::cout << std::boolalpha << (finish_applying(1) == 3) << std::endl; // true

auto plus2 = partial_apply(sum3)(1)(1);
std::cout << std::boolalpha << (plus2(1) == 3) << std::endl; // true
std::cout << std::boolalpha << (plus2(3) == 5) << std::endl; // true

Answer 8

Currying是一种减少函数的方法,该函数将多个参数带入一系列嵌套函数,每个参数都有一个参数:

full = (lambda a, b, c: (a + b + c))
print full (1, 2, 3) # print 6

# Curried style
curried = (lambda a: (lambda b: (lambda c: (a + b + c))))
print curried (1)(2)(3) # print 6

Currying很好,因为您可以使用预定义的值定义简单包装其他函数的函数,然后传递简化函数.C++ STL绑定器在C++中提供了这种实现.