C++ 递归lambdas

示例

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

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

但是lambda不能递归，它无法调用自身。Lambda没有名称，并且this在Lambda主体内使用是指捕获的内容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);
};

这可行，但应谨慎使用。它很慢（我们现在使用类型擦除来代替直接函数调用），它很脆弱（由于lambda引用原始对象，所以复制gcd或返回gcd会中断），并且不适用于泛型lambda。

使用两个智能指针：

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; // Lambda将存储在此处

    // 转发操作符()：
    template <class... Args>
    decltype(auto) operator()(Args&&... args) const {
        // 我们将自己传递给f，然后传递给参数。
        // the lambda should take the first argument as `auto&& recurse` or similar.
        return f(*this, std::forward<Args>(args)...);
    }
};
// 推断lambda类型的辅助函数：
template <class F>
y_combinator<std::decay_t<F>> make_y_combinator(F&& f) {
    return {std::forward<F>(f)};
}
// （请注意，在C ++ 17中，我们可以比`make_`函数做得更好）

我们可以实现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。当您想递归时，您将参数传递给递归。

所述y_combinator然后返回一个函数对象调用该函数与它的参数，但用合适的“递归”的对象（即y_combinator本身）作为它的第一个参数。它将y_combinator与之一起调用的其余参数也转发给lambda。

简而言之：

auto foo = make_y_combinator( [&](auto&& recurse, some arguments) {
  // 处理一些参数的写体
  // 当您想递归时，调用递归（其他一些参数）
});

并且您可以在lambda中进行递归，而没有严重的限制或明显的开销。