如何在 C 中进行柯里化？

Question

什么是咖喱？

如何在 C++ 中进行柯里化？

请解释 STL 容器中的活页夹？

原文由 yesraaj 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

简而言之，柯里化需要一个函数 f(x, y) 并给定一个固定的 Y ，给出一个新函数 g(x) 其中

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

这个新函数可以在只提供一个参数的情况下被调用，并将调用传递给带有固定 Y 参数的原始 f 函数。

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;
}

原文由 Greg Hewgill 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

1.什么是咖喱？

柯里化只是意味着将多个参数的函数转换为单个参数的函数。使用示例最容易说明这一点：

采用一个函数 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) 。

然后 f 的咖喱版本，我们称之为 curried_f=curry(f) 只需要一个参数，对应于 a f 的第一个参数，即参数 --- 。此外， f(1,"some string",19.7f) 也可以使用咖喱版本编写为 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++中如何实现柯里化？

以下有点复杂，但对我来说效果很好（使用c ++ 11）……它还允许像这样的任意程度的currying： 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 参数的剩余柯里化被委托给 _curry<Ts...> 的实现，并减少了一个模板参数。

c++14 / 17 的更新：

一个解决柯里化问题的新想法突然出现在我的脑海中……随着将 if constexpr 引入c ++ 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);
}

请参阅 此处 的实际代码。使用类似的方法， 这里 是如何使用任意数量的参数柯里化函数。

如果我们将 constexpr if needs_unapply<decltype(f)>::value 同样的想法似乎也适用于 C++14：

 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);
}

原文由 Julian 发布，翻译遵循 CC BY-SA 4.0 许可协议