6

在构建一个基于 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是开始递归的“主要” 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然而，被称为 like recurs(params...)。

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

我在这里想念什么？我怎样才能重写我的fold_l_impllambda，使其递归可以通过使用 Y Combinator 来概括？

4

1 回答 1

7

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

于 2016-02-24T17:39:01.303 回答