通过通用lambda理解Y Combinator

Question

在构建一个基于lambda的小型元编程库时,我有必要在C++ 14泛型lambda中使用递归来实现左折叠.

我自己的解决方案是将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是从递归开始的"主要"lambda.它返回一个具有所需左折签名的函数(累加器,当前项,剩余项......).

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

我最近遇到过这个想要在标准库中添加Y Combinator的提议,在阅读之后,它似乎与我在这里做的非常相似.

不幸的是,Y Combinator的概念仍然没有为我"点击" - 我遗漏了一些东西,我无法想象如何概括我self对任何函数的参数做了什么,避免了step样板.

我已经阅读了关于此事的优秀StackOverflow答案,但它仍然没有为我"点击".

(从那个答案)一个递归因子是这样定义的:

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 selflambda参数).

我在这里错过了什么？我怎么能fold_l_impl以这样的方式重写我的lambda,使得它的递归可以通过使用Y Combinator来推广？

Answer 1

这是一个组合,其中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作为第一个参数传递给它.