recursion in lambda

[alessio211734]

Hello guy,

I try to learn lamdba expression I need do some recursion inside the body of a function so I try to use lambda in this way:

auto expand = [&](CMeshO::VertexPointer vp, std::vector<CMeshO::VertexPointer> & region)
{
std::vector<CMeshO::VertexPointer> nearVerts;
MeshProcessing::nearVertex(vp, nearVerts);
for (auto v : nearVerts)
{
if (v->P().Y() < vp->P().Y())
{
region.push_back(v);
expand(v, region);
};
};
};

but I get some errors. So can I use lambda and recursion? I use visual studio 2015.

[Jorgen Grahn]

On Tue, 2018-04-03, alessio211734 wrote:
> Hello guy,
>
> I try to learn lamdba expression I need do some recursion inside the
> body of a function so I try to use lambda in this way:
>
> auto expand = [&](CMeshO::VertexPointer vp,
> std::vector<CMeshO::VertexPointer> & region)

You don't seem to need to capture anything, so replace [&] with [].

> {
> std::vector<CMeshO::VertexPointer> nearVerts;
> MeshProcessing::nearVertex(vp, nearVerts);
> for (auto v : nearVerts)
> {
> if (v->P().Y() < vp->P().Y())
> {
> region.push_back(v);
> expand(v, region);
> };
> };
> };
>
> but I get some errors.

It's very helpful to list the errors, not just mention you get errors.

> So can I use lambda and recursion? I use visual studio 2015.

I note that your code is similar to

int expand = foo(expand);

i.e. you use expand before it has been defined. I'm not sure what the
workaround would be, but I suspect that's the error.

/Jorgen

--
// Jorgen Grahn <grahn@ Oo o. . .
\X/ snipabacken.se> O o .

[alessio211734]

Error C3493 'expand' cannot be implicitly captured because no default capture mode has been specified ToothSection
expand(v, region);

Error C2064 term does not evaluate to a function taking 2 arguments
expand(vp, region);

[Ben Bacarisse]

The trouble is you are trying to use expand before it's type can be
deduced.

One solution would be to avoid using auto. To do this you pretty much
have to use std::function because lambdas that have a capture are not
convertible to function pointers. To take a simpler example:

std::function<int(int)> f = [&f](int n) {
return n < 1 ? 1 : n * f(n-1);
};

If the lambda has no capture, f could be a pointer to function object,
but then you could not refer to f in the body.

There are some tricks you can play that simulate the effect of a Y
combinator, but these appeal to me simply on academic grounds. For
example I enjoyed the fact that this works with gcc:

auto f = [](int n, auto g){
if (n < 1) return 1;
else return n * g(n-1, g);
};

where the call now becomes f(5, f);

However, switching back to the big picture, if expand is the only thing
captured, why not write a named function to do this?

--
Ben.

[Jorgen Grahn]

On Tue, 2018-04-03, Jorgen Grahn wrote:
> On Tue, 2018-04-03, alessio211734 wrote:

...

>> So can I use lambda and recursion? I use visual studio 2015.
>
> I note that your code is similar to
>
> int expand = foo(expand);
>
> i.e. you use expand before it has been defined. I'm not sure what the
> workaround would be, but I suspect that's the error.

I got no complaints, but based on Ben's later response the analysis
above seems to be incorrect.

[alessio211734]

Il giorno mercoledì 4 aprile 2018 09:16:58 UTC+2, Jorgen Grahn ha scritto:
> On Tue, 2018-04-03, Jorgen Grahn wrote:
> > On Tue, 2018-04-03, alessio211734 wrote:
> ...
> >> So can I use lambda and recursion? I use visual studio 2015.
> >
> > I note that your code is similar to
> >
> > int expand = foo(expand);

I declare the lambda before and work: post my new code

std::function<void(CMeshO::VertexPointer vp, std::vector<CMeshO::VertexPointer> & region)> expand;
expand = [&](CMeshO::VertexPointer vp, std::vector<CMeshO::VertexPointer> & region)->void {

std::vector<CMeshO::VertexPointer> nearVerts;
MeshProcessing::nearVertex(vp, nearVerts);

vp->SetS();
for (auto v : nearVerts)
{
if (!v->IsS())

[Chris Vine]

There was a proposal to add a Y-combinator to the standard library:
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0200r0.html .
I don't know what became of it.

However, there is a sample implementation which it says can be
implemented in C++11/14 and which might interest you.

Chris

[Ben Bacarisse]

Chris Vine <chris@cvine--nospam--.freeserve.co.uk> writes:

> On Wed, 04 Apr 2018 00:03:37 +0100
> Ben Bacarisse <ben....@bsb.me.uk> wrote:

(About recursive lambdas)
<snip>

>> One solution would be to avoid using auto. To do this you pretty much
>> have to use std::function because lambdas that have a capture are not
>> convertible to function pointers. To take a simpler example:
>>
>> std::function<int(int)> f = [&f](int n) {
>> return n < 1 ? 1 : n * f(n-1);
>> };
>>
>> If the lambda has no capture, f could be a pointer to function object,
>> but then you could not refer to f in the body.
>>
>> There are some tricks you can play that simulate the effect of a Y
>> combinator, but these appeal to me simply on academic grounds. For
>> example I enjoyed the fact that this works with gcc:
>>
>> auto f = [](int n, auto g){
>> if (n < 1) return 1;
>> else return n * g(n-1, g);
>> };
>>
>> where the call now becomes f(5, f);
>>
>> However, switching back to the big picture, if expand is the only
>> thing captured, why not write a named function to do this?
>
> There was a proposal to add a Y-combinator to the standard library:
> http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0200r0.html .
> I don't know what became of it.
>
> However, there is a sample implementation which it says can be
> implemented in C++11/14 and which might interest you.

Yes, thanks. That was interesting. The document is, in effect, an
extended answer to the OP's question.

The proposed "combinator" essentially automates what I was doing with f
and g above and the suggested implementation does indeed work, though I
think it needs C++14.

Cutting and pasting the definition from that document, I can write:

auto f = std::y_combinator(
[](auto f, int n) -> int { return n < 1 ? 1 : n * f(n-1); }
);
std::cout << f(5) << "\n";

though gcc (v6.3 at least) is unable to deduce the type without the
-> int in there.

--
Ben.