c++ - Lambda length of Linked List

Question

Consider the following definition for the node of a Linked List:

struct Node
{
    int data;
    struct Node *next;
};

I am new to c++ and coming from functional programming. I wish to write a lambda to compute the length of a linked list. I wrote:

auto listLength = [](Node * list){
    if(list == NULL) return 0;
    else return 1 + listLength(list -> next);
};

error: variable 'lengthList' declared with 'auto' type cannot appear in its own initializer

If I change from auto to int I get:

 error: called object type 'int' is not a function or function pointer

What is the issue?

`lengthList` is incongruent with `listLength`, are you sure you are showing the relevant code here? — πάντα ῥεῖ, Jun 05 '16 at 19:55
The question is correct. But I would recommend you to replace recursion to the `while` loop. It is more safe and faster. And replace `NULL` to `nullptr` :) — Dmitriy Zapevalov, Jun 05 '16 at 20:18

score 2 · Accepted Answer · answered Jun 05 '16 at 20:00

2

The issue is twofold:

1) A lambda needs to capture any object that's defined outside of the lambda.

2) The definition of listLength isn't complete until the end of the entire variable declaration.

It's sort of a chicken-vs-egg problem. The cleanest solution is to use std::function:

#include <functional>

std::function< int (Node *)> listLength;

listLength = [&](Node * list){
    if(list == NULL) return 0;
    else return 1 + listLength(list -> next);
};

answered Jun 05 '16 at 20:00

Sam Varshavchik

114,536
5
94
148

where can I find documentation and/or explanation about this? – mastro Jun 05 '16 at 20:02
1

This is C++11, so any C++ book that's been updated to at least the C++11 standard. – Sam Varshavchik Jun 05 '16 at 20:03
When you make a declaration "type name=value", the "name" part isn't defined until ***after*** this declaration. Your initial attempt tried to use "listlength" before it was actually defined. That was one of the problems with your initial approach. – Sam Varshavchik Jun 05 '16 at 20:05
@P0W I had already found that but it does not actually explain the use of the capturing function std::function – mastro Jun 05 '16 at 20:07
I am using " a Tour of C++" but the capturing std::function is not explained there – mastro Jun 05 '16 at 20:08
Capturing refers to the lambda itself. In order for the lambda to use any object that's not declared by the lambda itself, it must be captured. "listlength" is an object declared outside of the body of the lambda itself, hence it must be captured, in order for it to be used inside the body of the lambda. – Sam Varshavchik Jun 05 '16 at 20:14

c++ - Lambda length of Linked List

1 Answers1