通过通用lambdas了解Y Combinator [英] Understanding Y Combinator through generic lambdas

问题描述

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

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...);
}

mainlambda从递归开始。它返回一个具有所需左边签名（累加器，当前项，剩余项...）的函数。

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.

（从该答案）递归因子定义如下：

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

recurs 参数似乎有相同的角色作为我的 self 参数。我不明白是如何调用而不是再次将重复插入自身。

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 ...） code>。

recurs, however, is called like recurs(params...).

尝试调用 self（params ...）会导致编译器错误me 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?

推荐答案

这里是ay组合，其中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.

这篇关于通过通用lambdas了解Y Combinator的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！