通过通用 lambda 理解 Y Combinator

Question

在构建基于 lambda 的小型元编程库时，我有必要在 C++14 通用 lambda 中使用递归来实现 left-fold.

我自己的解决方案是将 lambda 本身作为其参数之一传递，如下所示：

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 是开始递归的 "main" lambda。它 returns 具有所需左折叠签名的函数 （累加器、当前项、剩余项...）。

函数使用self(self)(next, y_xs...)递归调用自身。

最近遇到this proposal想在标准库中加入一个Y Combinator，看了之后觉得和我的极其相似我在这里做。

不幸的是，Y Combinator 的概念仍然不适合我 "click" - 我遗漏了一些东西，我无法想象如何概括我对任何函数的 self 参数所做的事情, 避免 step 样板。

我已经阅读了 this excellent Whosebug answer 关于此事的内容，但它仍然没有 "click" 对我来说。

（来自那个答案） 递归阶乘是这样定义的：

fact =
  (recurs) =>
    (x) =>
      x == 0 ? 1 : x * recurs(x - 1);

recurs参数好像和我的self参数作用一样。我不明白的是如何在不将 recurs 再次传递给自身的情况下调用 recurs。

我必须这样调用 self：self(self)(params...)。

然而，

recurs 被称为 recurs(params...)。

尝试调用 self(params...) 导致编译器错误，通知我 self 只需要一个参数 （即 auto self lambda 参数）.

我在这里错过了什么？我如何重写我的 fold_l_impl lambda，使其递归可以通过使用 Y Combinator 进行泛化？

Answer 1

这是一个 y 组合，其中 lambda 传递了一个递归，不需要传递递归：

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。

通过通用 lambda 理解 Y Combinator

Understanding Y Combinator through generic lambdas

c++

recursion

functional-programming

y-combinator

c++14