递归的 lambdas

Created: November-22, 2018

假设我们希望将 Euclid 的 gcd() 写为 lambda。作为一个功能，它是：

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a%b);
}

但是 lambda 不能递归，它无法调用自身。lambda 没有名称，并且在 lambda 的主体内使用 this 指的是捕获的 this（假设 lambda 是在成员函数的主体中创建的，否则它是一个错误）。那么我们如何解决这个问题呢？

使用 `std::function`

我们可以让 lambda 捕获对尚未构建的 std::function 的引用：

std::function<int(int, int)> gcd = [&](int a, int b){
    return b == 0 ? a : gcd(b, a%b);
};

这有效，但应谨慎使用。它很慢（我们现在使用类型擦除而不是直接函数调用），它很脆弱（复制 gcd 或返回 gcd 会因为 lambda 引用原始对象而中断），并且它不适用于通用 lambdas。

使用两个智能指针：

auto gcd_self = std::make_shared<std::unique_ptr< std::function<int(int, int)> >>();
*gcd_self = std::make_unique<std::function<int(int, int)>>(
  [gcd_self](int a, int b){
    return b == 0 ? a : (**gcd_self)(b, a%b);
  };
};

这增加了很多间接（这是开销），但可以复制/返回，并且所有副本共享状态。它确实让你返回 lambda，否则不如上面的解决方案脆弱。

使用 Y 组合器

借助简短的实用程序结构，我们可以解决所有这些问题：

template <class F>
struct y_combinator {
    F f; // the lambda will be stored here

    // a forwarding operator():
    template <class... Args>
    decltype(auto) operator()(Args&&... args) const {
        // we pass ourselves to f, then the arguments.
        // the lambda should take the first argument as `auto&& recurse` or similar.
        return f(*this, std::forward<Args>(args)...);
    }
};
// helper function that deduces the type of the lambda:
template <class F>
y_combinator<std::decay_t<F>> make_y_combinator(F&& f) {
    return {std::forward<F>(f)};
}
// (Be aware that in C++17 we can do better than a `make_` function)

我们可以实现我们的 gcd：

auto gcd = make_y_combinator(
  [](auto&& gcd, int a, int b){
    return b == 0 ? a : gcd(b, a%b);
  }
);

y_combinator 是 lambda 演算中的一个概念，它允许你在定义之前无法命名自己的递归。这正是 lambda 所具有的问题。

你创建一个 lambda，将 recurse 作为其第一个参数。当你想要递归时，你传递参数 recurse。

然后 y_combinator 返回一个函数对象，该函数对象使用其参数调用该函数，但使用合适的 recurse 对象（即 y_combinator 本身）作为其第一个参数。它将你称之为 y_combinator 的其余参数转发给 lambda。

简而言之：

auto foo = make_y_combinator( [&](auto&& recurse, some arguments) {
  // write body that processes some arguments
  // when you want to recurse, call recurse(some other arguments)
});

你有一个 lambda 递归，没有严重的限制或显着的开销。

使用 std::function

使用两个智能指针：

使用 Y 组合器

使用 `std::function`