Понимание Y Combinator через общие лямбды

Question

При создании небольшой библиотеки метапрограммирования, основанной на лямбда-выражениях, у меня была необходимость использовать рекурсию в обобщенной лямбда-выражении C++14 для реализации левой складки.

Мое собственное решение передавало саму лямбду как один из ее параметров, например так:

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 это "главная" лямбда, которая начинает рекурсию. Возвращает функцию с желаемой подписью влево (аккумулятор, текущий элемент, оставшиеся элементы...).

Функция вызывает себя рекурсивно, используя self(self)(next, y_xs...),

Недавно я наткнулся на это предложение, которое хочет добавить Y Combinator в Стандартную библиотеку, и после прочтения оно кажется очень похожим на то, что я делаю здесь.

К сожалению, концепция Y Combinator все еще не "щелкает" для меня - я что-то упустил и не могу представить, как обобщить то, что я сделал с self параметр для любой функции, избегая step шаблонный.

Я прочитал этот превосходный ответ Stackru по этому вопросу, но он все еще не "щелкнул" для меня.

(Из этого ответа) рекурсивный факториал определяется следующим образом:

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 лямбда-параметр).

Что мне здесь не хватает? Как я мог переписать мой fold_l_impl лямбда таким образом, чтобы его рекурсию можно было обобщить с помощью Y-комбинатора?

Answer 1

Вот комбинация, в которой лямбда передается рекурсорам, которые не нужно передавать рекурсорам:

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

хитрость здесь в том, что я использовал не-лямбда-объект-функцию, который имеет доступ к своему собственному thisкоторый я передаю f в качестве первого параметра.