BYR Achieve · 镜像论坛

求教，关于使用Y组合子实现lambda表达式递归的一段代码看不懂

2017/9/17镜像同步3 回复

需要实现的例子是辗转相除法求最大公约数： Let's say we wish to write Euclid's gcd() as a lambda. As a function, it is: int gcd(int a, int b) { return b == 0 ? a : gcd(b, a%b); } 这里使用Y组合子实现 Use a Y-combinator With the help of a short utility struct, we can solve all of these problems: 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) we can implement our gcd as: auto gcd = make_y_combinator( [](auto&& gcd, int a, int b){ return b == 0 ? a : gcd(b, a%b); } ); The y_combinator is a concept from the lambda calculus that lets you have recursion without being able to name yourself until you are defined. This is exactly the problem lambdas have. You create a lambda that takes "recurse" as its first argument. When you want to recurse, you pass the arguments to recurse. The y_combinator then returns a function object that calls that function with its arguments, but with a suitable "recurse" object (namely the y_combinator itself) as its first argument. It forwards the rest of the arguments you call the y_combinator with to the lambda as well. In short: 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) }); and you have recursion in a lambda with no serious restrictions or significant overhead. 主要有如下几个问题： 1、struct y_combinator 是如何在实现储存Y组合子的，看上去这个结构定义和Y组合子的定义没有多少关系。 2、decltype(auto)，为什么不直接用auto 3、std::decay_t<F>，为什么不能直接用F 代码来源：https://stackoverflow.com/documentation/c%2b%2b/572/lambdas/1854/what-is-a-lambda-expression#t=201709141450184452051

订阅后，新回复会通过你的通知中心匿名送达。