Understanding Y Combinator through generic lambdas

Question

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.

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 is the "main" lambda that starts off the recursion. It returns a function with the desired left-fold signature (accumulator, current item, remaining items...).

The function calls itself recursively by using self(self)(next, y_xs...).

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.

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.

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

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.

I have to call self like this: self(self)(params...).

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

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

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?

Binary

Answer 1

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

then you do:

  return y_combinate(step)(acc, xs...);

and change

                   return self(self)(next, y_xs...);

to

                   return self(next, y_xs...);

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.

Cursed

Thanks, I get it now! It "clicked" when I realized that what I wanted to do was get the *this of a lambda, which is not possible at the moment. – Binary

@VittorioRomeo As an aside, self should be taken as auto&& self not auto self. – Cursed

Why std::decay_t<F>? Is it important to copy f? – Country

@Country Because I'm storing it and returning it? Storing and returning a reference deduced from a function argument in generic code is a bad idea, in my experience. Imagine auto fib(){ auto internal = [](auto&& self, int x){ if (x<2) return 1; return self(x-1)+self(x-2); }; return y_combinate(internal); } -- we want the lambda to live as long as the return type, not only as long as internal. – Cursed

@Yakk Maybe that's just a general language limitation then. On the one hand, sometimes you make unnecessary copies. On the other hand, sometimes you dangle references? – Country

@Country Yes. If we could add in a "return value lifetime depends upon lifetime of argument" it would help; but even then, it doesn't solve the fib() code above (where the returned object needs to be bigger and carry the lambda with it!) other than possibly generating a warning (returning value whose lifetime depends on a temporary). However, if a caller wants to avoid creating that copy, they can y_combinate(std::cref(f)), and the returned function object will only hold a (constant reference to) f, not a copy, and it will work. – Cursed