通过泛型 lambda 理解 Y Combinator
在构建一个基于 lambda 的小型元编程库时，我有必要在 C++14 通用 lambda 中使用递归来实现一个 左折叠.
While building a small lambda-based metaprogramming library, I had the necessity of using recursion in a C++14 generic lambda, to implement a left-fold.
我自己的解决方案是将 lambda 本身作为其参数之一传递，如下所示:
My own solution was passing the lambda itself as one of its parameters, like this:
template <typename TAcc, typename TF, typename... Ts>
constexpr auto fold_l_impl(TAcc acc, TF f, Ts... xs)
{
// Folding step.
auto step([=](auto self)
{
return [=](auto y_acc, auto y_x, auto... y_xs)
{
// Compute next folding step.
auto next(f(y_acc, y_x));
// Recurse if required.
return static_if(not_empty(y_xs...))
.then([=]
{
// Recursive case.
return self(self)(next, y_xs...);
})
.else_([=]
{
// Base case.
return next;
})();
};
});
// Start the left-fold.
return step(step)(acc, xs...);
}
step 是开始递归的主要"lambda.它返回一个具有所需左折叠签名的函数(累加器，当前项目，剩余项目...).
step is the "main" lambda that starts off the recursion. It returns a function with the desired left-fold signature (accumulator, current item, remaining items...).
该函数使用self(self)(next, y_xs...)递归调用自身.
The function calls itself recursively by using self(self)(next, y_xs...).
我最近遇到了这个提议想在标准库中加入一个Y Combinator，看了之后，和我在这里做的事情非常相似.
I've recently come across this proposal that wants to add a Y Combinator to the Standard Library, and after reading it, it seems extremely similar to what I am doing here.
不幸的是，Y Combinator 的概念对我来说仍然没有点击"――我遗漏了一些东西，我无法想象如何概括我对任何函数的 self 参数所做的事情，避免 step 样板.
Unfortunately, the concept of the Y Combinator still doesn't "click" for me - I am missing something and I cannot visualize how to generalize what I did with the self parameter for any function, avoiding the step boilerplate.
我已经阅读了关于此事的这个优秀的 StackOverflow 答案，但它仍然没有'为我点击".
I've read this excellent StackOverflow answer regarding the matter, but it still didn't "click" for me.
(来自那个答案) 递归阶乘是这样定义的:
(From that answer) a recursive factorial is defined this way:
fact =
(recurs) =>
(x) =>
x == 0 ? 1 : x * recurs(x - 1);
recurs 参数似乎与我的 self 参数具有相同的作用.我不明白的是如何在不将 recurs 再次传入自身的情况下调用 recurs.
The recurs parameter seems to have the same role as my self parameter. What I do not understand is how recurs is called without passing recurs into itself again.
我必须像这样调用 self:self(self)(params...).
I have to call self like this: self(self)(params...).
recurs 的调用方式类似于 recurs(params...).
recurs, however, is called like recurs(params...).
尝试调用 self(params...) 会导致编译器错误，通知我 self 只需要一个参数 (这是 auto self lambda 参数).
Attempting to call self(params...) results in a compiler error informing me that self requires only a single parameter (which is the auto self lambda parameter).
我在这里错过了什么?我怎样才能重写我的 fold_l_impl lambda，使其递归可以通过使用 Y Combinator 来泛化?
What am I missing here? How could I rewrite my fold_l_impl lambda in such a way that its recursion could be generalized through the use of a Y Combinator?
推荐答案
这里是一个 y 组合，其中 lambda 被传递一个不需要传递的递归:
Here is a y combinate where the lambda is passed a recurs that doesn't need to be passed recurs:
template<class F>
struct y_combinate_t {
F f;
template<class...Args>
decltype(auto) operator()(Args&&...args)const {
return f(*this, std::forward<Args>(args)...);
}
};
template<class F>
y_combinate_t<std::decay_t<F>> y_combinate( F&& f ) {
return {std::forward<F>(f)};
};
然后你做:
return y_combinate(step)(acc, xs...);
和改变
return self(self)(next, y_xs...);
到
return self(next, y_xs...);
这里的技巧是我使用了一个非 lambda 函数对象，它可以访问自己的 this，我将其作为第一个参数传递给 f.
the trick here is I used a non-lambda function object that has access to its own this, which I pass to f as its first parameter.
相关文章