How to implement a method that creates a recursive lambda and returns it

Question

I found a post on how to create a recursive lambda, but it is not clear how to return it from a function.

As far as I see, in the code below, captured func refers to a destroyed object:

#include <iostream>
#include <functional>

std::function<int (int)> make_lambda()
{
    std::function<int (int)> func;
    
    func = [&func](int val)
    {
        if (val < 10)
        {
            return func(val + 1);
        }
        
        return val;
    };
    
    return func;
}

int main()
{
    std::cout << make_lambda()(0);
    
    return 0;
}

How to make this code work?

Is there a better way than using std::shared_pointer<std::function<int (int)>>?

void make_lambda(std::function<int (int)>&) is not an option.

EDIT1:

Why is there no this allowing lambdas to refer to themselves?

Yakk - Adam Nevraumont · Accepted Answer · 2021-09-03T02:42:51.817

6

The Y combinator is your friend.

template<class R, class...Args>
auto Y = [] (auto f) {
  auto action = [=] (auto action) -> std::function<R(Args...)> {
    return [=] (Args&&... args)->R {
      return f( action(action), std::forward<Args>(args)... );
    };
  };
  return action(action);
};

now just:

return Y<int, int>([](auto&& self, int val)
{
    if (val < 10)
    {
        return self(val + 1);
    }
    
    return val;
});

and poof, magic.

You can't use this in a lambda to refer to the lambda itself, because it refers to enclosing objects this.

The explicit this argument proposal would let you avoid this problem. But that isn't in c++20.

Last I checked, the syntax looked a bit like:

return [](this auto&& self, int val) {
  if (val < 10)
    return self(val+1);
  return val;
};

where your *this parameter was passed as the first argument, including its r/lvalue category.

edited Sep 03 '21 at 02:42

answered Sep 03 '21 at 00:09

Yakk - Adam Nevraumont

262,606
27
330
524

Trying to figure out what is `action(action)` – Dmitriano Sep 03 '21 at 11:21
1

@Dmitriano `action(action)` is a `std::function` (look at the definition of `action`; it always returns that type). In particular, it is the return value from `Y`. It is strangely named because I wrote this Y combinator using lambdas, who have no access to `*this`. `Y` is a lambda containing a lambda containing a lambda, and takes a lambda as an argument, and one of the inner lambdas takes a different lambda (itself), and another passes a lambda to a lambda... so the level of indirection sort of explode. A simpler version can be written, but it is longer and less cute. – Yakk - Adam Nevraumont Sep 03 '21 at 12:11

How to implement a method that creates a recursive lambda and returns it

1 Answers1