65.9K
CodeProject 正在变化。 阅读更多。
Home

C++14 中的柯里化和部分应用

BlackMATov
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.71/5 (10投票s)

2019年1月17日

CPOL

9分钟阅读

viewsIcon

17747

C++ 中柯里化选项和函数部分应用之一，这是我个人最喜欢的

引言

在这篇文章中，我将向您介绍 C++ 中 currying 的一种选择和函数的部分应用，这是我个人最喜欢的一种方式。我还会展示我自己对这种方法的初步实现，并用非常简单的语言解释 currying 的要点，而无需复杂的数学公式。我们还将了解我们将用于 currying 函数的 kari.hpp 库的内部工作原理。总之，里面有很多有趣的内容，欢迎阅读！

柯里化

那么，currying 是什么？我想这是您从 Haskell 程序员那里经常听到的词之一（当然，在 monad 之后）。本质上，这个术语的定义非常简单，因此已经使用 ML 类型语言或 Haskell 编写过代码，或者已经从其他地方了解过其含义的读者，可以随时跳过本节。

Currying - 这是一种将接受 N 个参数的函数转换为一个函数的技术，该函数接受单个参数并返回下一个参数的函数，依此类推，直到返回最后一个参数的函数，该函数将代表整体结果。我认为举例说明会有帮助

int sum2(int lhs, int rhs) {
  return lhs + rhs;
}

这里我们有一个二元加法函数。如果我们想将其转换为单变量函数该怎么办？这实际上非常简单

auto curried_sum2(int lhs) {
  return [=](int rhs) {
    return sum2(lhs, rhs);
  };
}

不，我们做了什么？我们根据一个名为 lambda 的单个参数获取了一个值，该 lambda 又接受第二个参数并执行加法本身。结果是，我们可以逐个将 curried 函数 curried_sum2 应用于我们的参数

// output: 42
std::cout << sum2(40, 2) << std::endl;
std::cout << curried_sum2(40)(2) << std::endl;

这实际上是 currying 操作的全部意义。当然，对于任何 元数 的函数都可以这样做 - 它将以完全相同的方式工作。每次我们从另一个参数获取值时，我们将返回一个 N-1 个参数的 curried 函数

auto sum3(int v1, int v2, int v3) {
  return v1 + v2 + v3;
}

auto curried_sum3(int v1) {
  return [=](int v2){
    return [=](int v3){
      return sum3(v1, v2, v3);
    };
  };
}

// output: 42
std::cout << sum3(38, 3, 1) << std::endl;
std::cout << curried_sum3(38)(3)(1) << std::endl;

部分应用

偏函数应用 - 这是一种调用 N 个参数的函数的方式，此时只接受部分参数并返回剩余参数的另一个函数。

在这方面，应该注意的是，在 Haskell 等语言中，这个过程会自动进行，在程序员不知情的情况下。我们这里要做的是显式地执行它，也就是说，像这样调用我们的 sum3 函数：sum3(38,3)(1)，或者像这样：sum3(38)(3,1)。此外，如果一个函数返回另一个已 curried 的函数，它也可以使用第一个函数的参数列表来调用。我们来看一个例子

int boo(int v1, int v2) {
  return v1 + v2;
}

auto foo(int v1, int v2) {
  return kari::curry(boo, v1 + v2);
}

// output: 42
std::cout << kari::curry(foo)(38,3,1) << std::endl;
std::cout << kari::curry(foo)(38,3)(1) << std::endl;
std::cout << kari::curry(foo)(38)(3,1) << std::endl;

我们在这里实际上已经有点超前了，展示了一个 kari.hpp 用法的示例，所以是的，它确实做到了。

设定目标

在我们编写任何内容之前，有必要（或期望）了解我们最终想要拥有什么。我们想要能够 currying 和部分应用任何可在 C++ 中调用的函数。这些函数包括

  • lambda 表达式（包括泛型 lambda）
  • 函数对象（仿函数）
  • 任意元数的函数（包括模板）
  • 可变参数函数
  • 类的方法

可以通过指定要 currying 的确切参数数量来 currying 可变参数函数。还期望与 std::bind 及其结果进行标准交互。当然，我们需要有机会应用多变量函数并调用嵌套函数，这样看起来就像我们在处理一个 curried 函数。

而且我们不能忘记性能。我们需要最大程度地减少包装器、参数传递和存储的计算成本。这意味着我们需要移动而不是复制，只存储我们真正需要的东西，并尽快返回（并随后移除）数据。

作者，您又在尝试发明 std::bind 了！

是，也不是。std::bind 无疑是一个强大且久经考验的工具，我无意写它的替代品或杀手。是的，它可以用于 currying 和显式偏函数应用（指定要应用哪些参数、在哪里应用以及应用多少）。但它绝对不是最方便的方法，更不用说它并不总是适用的，因为我们必须知道函数的元数并根据其编写特定的绑定。例如

int foo(int v1, int v2, int v3, int v4) {
  return v1 + v2 + v3 + v4;
}

// std::bind
auto c0 = std::bind(foo, _1, _2, _3, _4);
auto c1 = std::bind(c0, 15, _1, _2, _3);
auto c2 = std::bind(c1, 20, 2, _1);
auto rr = c2(5);
std::cout << rr << std::endl; // output: 42

// kari.hpp
auto c0 = kari::curry(foo);
auto c1 = c0(15);
auto c2 = c1(20, 2);
auto rr = c2(5);
std::cout << rr << std::endl; // output: 42

API

namespace kari {
  template < typename F, typename... Args >
  constexpr decltype(auto) curry(F&& f, Args&&... args) const;

  template < typename F, typename... Args >
  constexpr decltype(auto) curryV(F&& f, Args&&... args) const;

  template < std::size_t N, typename F, typename... Args >
  constexpr decltype(auto) curryN(F&& f, Args&&... args) const;

  template < typename F >
  struct is_curried;

  template < typename F >
  constexpr bool is_curried_v = is_curried<F>::value;

  template < std::size_t N, typename F, typename... Args >
  struct curry_t {
    template < typename... As >
    constexpr decltype(auto) operator()(As&&... as) const;
  };
}
kari::curry(F&& f, Args&&... args)

返回一个 curry_t 类型（curried 函数）的函数对象，带有可选的参数 args 应用，或者将给定函数 f 应用于参数的结果（如果函数是零参数函数，或者传递的参数足以调用它）。

如果 f 参数包含一个已经 curried 的函数，它将返回该函数的副本，并应用参数 args。

kari::curryV(F&& f, Args&&... args)

允许 currying 具有可变数量参数的函数。之后，这些函数可以使用 () 运算符在没有参数的情况下调用。例如

auto c0 = kari::curryV(std::printf, "%d + %d = %d");
auto c1 = c0(37, 5);
auto c2 = c1(42);
c2(); // output: 37 + 5 = 42

如果 f 参数包含一个已经 curried 的函数，它将返回该函数的副本，其可变数量参数的应用类型已更改，并应用参数 args。

kari::curryN(F&& f, Args&&... args)

允许通过指定要应用的参数数量 N（不包括 args 中给出的参数）来 currying 具有可变数量参数的函数。例如

char buffer[256] = {'\0'};
auto c = kari::curryN<3>(std::snprintf, buffer, 256, "%d + %d = %d");
c(37, 5, 42);
std::cout << buffer << std::endl;  // output: 37 + 5 = 42

如果 f 参数包含一个已经 curried 的函数，它将返回该函数的副本，其 N 个参数的应用类型已更改，并应用参数 args。

kari::is_curried<F>, kari::is_curried_v<F>

一些辅助结构，用于检查函数是否已被 curried。例如

const auto l = [](int v1, int v2){
  return v1 + v2;
};
const auto c = curry(l);

// output: is `l` curried? no
std::cout
  << "is `l` curried? "
  << (is_curried<decltype(l)>::value ? "yes" : "no")
  << std::endl;

// output: is `c` curried? yes
std::cout
  << "is `c` curried? "
  << (is_curried_v<decltype(c)> ? "yes" : "no")
  << std::endl;
kari::curry_t::operator()(As&&... as)

允许对 curried 函数进行完整或部分应用的运算符。返回初始函数 F 的剩余参数的 curried 函数，或者通过将其应用于旧参数和新参数 as 的积压中获得的该函数的值。例如

int foo(int v1, int v2, int v3, int v4) {
  return v1 + v2 + v3 + v4;
}

auto c0 = kari::curry(foo);
auto c1 = c0(15, 20); // partial application
auto rr = c1(2, 5); // function call - foo(15,20,2,5)
std::cout << rr << std::endl; // output: 42

如果您使用 curryV 或 curryN 调用没有参数的 curried 函数，如果参数足够，它将被调用。否则，它将返回一个部分应用的函数。例如

auto c0 = kari::curryV(std::printf, "%d + %d = %d");
auto c1 = c0(37, 5);
auto c2 = c1(42);

// force call variadic function std::printf
c2(); // output: 37 + 5 = 42

实现细节

在提供实现细节时，我将使用 C++17 来缩短文章篇幅，避免不必要的解释和堆积的 SFINAE，以及我在 C++14 标准中不得不添加的实现示例。所有这些您都可以在项目 存储库 中找到，您也可以在那里将其添加到您的收藏夹。:)

make_curry(F&& f, std::tuple<Args...>&& args)

一个辅助函数，它创建一个函数对象 curry_t 或将给定的函数 f 应用于参数 args。

template < std::size_t N, typename F, typename... Args >
constexpr auto make_curry(F&& f, std::tuple<Args...>&& args) {
  if constexpr ( N == 0 && std::is_invocable_v<F, Args...> ) {
    return std::apply(std::forward<F>(f), std::move(args));
  } else {
    return curry_t<
      N,
      std::decay_t<F>,
      Args...
    >(std::forward<F>(f), std::move(args));
  }
}

template < std::size_t N, typename F >
constexpr decltype(auto) make_curry(F&& f) {
  return make_curry<N>(std::forward<F>(f), std::make_tuple());
}

现在，关于这个函数有两个有趣的地方

  • 仅当它对这些参数可调用且应用计数器 N 为零时，我们才将其应用于参数。
  • 如果函数不可调用，我们将其视为部分应用，并创建一个包含函数和参数的函数对象 curry_t。
struct curry_t

该函数对象应存储参数的积压和我们将最终调用该函数时的函数。这个对象就是我们将调用并部分应用的。

template < std::size_t N, typename F, typename... Args >
struct curry_t {
  template < typename U >
  constexpr curry_t(U&& u, std::tuple<Args...>&& args)
  : f_(std::forward<U>(u))
  , args_(std::move(args)) {}
private:
  F f_;
  std::tuple<Args...> args_;
};

我们之所以将参数的积压 args_ 存储在 std::tuple 中，有几个原因

  1. 自动处理带 std::ref 的情况，以便在需要时存储引用，默认基于值
  2. 根据其参数方便地应用函数（std::apply）
  3. 它是现成的，所以您不必从头写 :)

我们也将调用对象和函数 f_ 按值存储，并在创建对象时注意选择类型（我将在下面详细介绍此问题），或者使用构造函数中的 通用引用 进行移动或复制。

模板参数 N 作为可变参数函数的应用计数器。

curry_t::operator()(const As&...)

当然，让这一切工作起来的关键是调用函数对象的运算符。

template < std::size_t N, typename F, typename... Args >
struct curry_t {
  // 1
  constexpr decltype(auto) operator()() && {
    return detail::make_curry<0>(
      std::move(f_),
      std::move(args_));
  }

  // 2
  template < typename A >
  constexpr decltype(auto) operator()(A&& a) && {
    return detail::make_curry<(N > 0 ? N - 1 : 0)>(
      std::move(f_),
      std::tuple_cat(
        std::move(args_),
        std::make_tuple(std::forward<A>(a))));
  }

  // 3
  template < typename A, typename... As >
  constexpr decltype(auto) operator()(A&& a, As&&... as) && {
    return std::move(*this)(std::forward<A>(a))(std::forward<As>(as)...);
  }

  // 4
  template < typename... As >
  constexpr decltype(auto) operator()(As&&... as) const & {
    auto self_copy = *this;
    return std::move(self_copy)(std::forward<As>(as)...);
  }
}

调用运算符有四个重载函数。

  1. 一个不带参数的函数，允许启动应用可变参数函数（由 curryV 或 curryN 创建）。在这里，我们将应用计数器减至零，使其清楚函数已准备好应用，然后我们将所有必需的参数传递给 make_curry 函数。

  2. 一个带单个参数的函数，它将应用计数器减 1（如果它不为零），并将我们的新参数 a 放入参数积压 args_ 中，并将所有这些传递给 make_curry。

  3. 一个可变参数函数，它实际上是部分应用各种参数的技巧。它所做的是递归地一个一个地应用它们。现在，它们不能一次性应用有两个原因

    • 在没有剩余参数之前，应用计数器可能会减到零。
    • 函数 f_ 可能会提前被调用并返回另一个 curried 函数，因此所有后续参数都将用于它。

  4. 最后一个函数充当了使用 lvalue 调用 curry_t 和使用 rvalue 调用函数之间的桥梁。

对 ref-qualified 函数的标签使整个过程几乎像魔法一样。简而言之，借助它们，我们得知一个对象是使用 rvalue 引用调用的，我们可以在最终调用函数 make_curry 时移动参数而不是复制它们。否则，我们将不得不复制参数，以便仍然有机会再次调用此函数，确保参数仍然存在。

奖励

在继续结论之前，我想向您展示几个 kari.hpp 中的语法糖示例，这些可以被视为奖励。

运算符节

已经使用 Haskell 编程的程序员应该熟悉运算符节，它们允许对应用的运算符进行简短描述。例如，结构 (*2) 生成一个单参数函数，返回该参数乘以 2 的结果。那么，我想尝试在 C++ 中写一些类似的东西。说干就干！

using namespace kari::underscore;
std::vector<int> v{1,2,3,4,5};
std::accumulate(v.begin(), v.end(), 0, _+_);        // result: 15
std::transform(v.begin(), v.end(), v.begin(), _*2); // v = 2, 3, 6, 8, 10
std::transform(v.begin(), v.end(), v.begin(), -_);  // v = -2,-3,-6,-8,-10

函数组合

当然，如果我没有尝试编写 函数组合，我将是不完整的疯子。作为组合运算符，我选择了 operator *，因为它是我在所有可用符号中外观上最接近数学中的组合符号的。我还使用它来将结果函数应用于参数。所以，这就是我的成果

using namespace kari::underscore;

// 1
std::cout << (_*2) * (_+2) * 4 << std::endl; // output: 12

// 2
std::cout << 4 * (_*2) * (_+2) << std::endl; // output: 10
  1. 函数 (*2) 和 (+2) 的组合应用于 4。(4 + 2) * 2 = 12
  2. 函数 (*2) 应用于 4，然后我们将 (+2) 应用于结果。(4 * 2 + 2) = 10

同样，您也可以在 pointfree 风格 中构建相当复杂的组合，但请记住，只有 Haskell 程序员才能理解这些。:)

// (. (+2)) (*2) $ 10 == 24 // haskell analog
std::cout << (_*(_+2))(_*2) * 10 << std::endl; // output: 24

// ((+2) .) (*2) $ 10 == 22 // haskell analog
std::cout << ((_+2)*_)(_*2) * 10 << std::endl; // output: 22

结论

我认为之前已经很清楚，在实际项目中没有必要使用这些技术。但仍然，我必须提到这一点。毕竟，我的目标是证明自己并测试新的 C++ 标准。我能做到吗？ C++ 也能做到吗？我想，您刚刚看到了我们两者都 kind of 做到了。我非常感谢所有阅读全文的人。

历史

  • 2019年1月17日：初版
© . All rights reserved.