問題描述

在構建一個基于 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.

這篇關于通過泛型 lambda 理解 Y Combinator的文章就介紹到這了，希望我們推薦的答案對大家有所幫助，也希望大家多多支持html5模板網！