C++2a recursive lambda within a function

Question

I am trying to get this to compile:

#include <algorithm>
#include <climits>
#include <iostream>
#include <iterator>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>
using namespace std;


bool isInterleave(string &s1, string &s2, string &s3) {
  auto dfs = [&](int i, int j, int k) {
    if (k > s3.length()) {
      return true;
    }
    if (s1[i] == s3[k]) {
      auto res = dfs(i + 1, j, k + 1);

    }
  };

  dfs(0, 0);
}

I get an error:


x86-64 gcc 9.3

-pedantic -Wall -O2 -std=c++2a
Could not execute the program

Compiler returned: 1

Compiler stderr

<source>: In lambda function:

<source>:14:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]

   14 |     if (k > s3.length()) {

      |         ~~^~~~~~~~~~~~~

<source>:18:18: error: use of 'dfs' before deduction of 'auto'

   18 |       auto res = dfs(i + 1, j, k + 1);

      |                  ^~~

<source>: In function 'bool isInterleave(std::string&, std::string&, std::string&)':

<source>:23:11: error: no match for call to '(isInterleave(std::string&, std::string&, std::string&)::<lambda(int, int, int)>) (int, int)'

   23 |   dfs(0, 0);

      |           ^

<source>:13:14: note: candidate: 'isInterleave(std::string&, std::string&, std::string&)::<lambda(int, int, int)>'

   13 |   auto dfs = [&](int i, int j, int k) {

      |              ^

<source>:13:14: note:   candidate expects 3 arguments, 2 provided

<source>:24:1: warning: no return statement in function returning non-void [-Wreturn-type]

   24 | }

      | ^

How do I fix this?

You can't use dfs until its type has been determined, and you left it to the compiler to work out what it returns, which it can't until it has determined what it returns. — molbdnilo
– molbdnilo, Commented May 8, 2020 at 12:19
You have also forgotten that a function that is supposed to return something must do that. — molbdnilo
– molbdnilo, Commented May 8, 2020 at 12:21
Does this answer your question? Recursive lambda functions in C++11 — bitmask
– bitmask, Commented May 8, 2020 at 13:04

Ted Lyngmo · Accepted Answer · 2022-09-07 22:46:16Z

6

'dfs' declared with deduced type 'auto' cannot appear in its own initializer

With recursive lambdas you can use std::function to provide the signature so it doesn't have to be deduced:

#include <functional>
#include <string>

bool isInterleave(std::string &s1, std::string &s2, std::string &s3) {

  std::function<bool(int, int, int)> dfs = [&](int i, int j, int k) {
    if (k > s3.length()) {
      return true;
    }

    // what should the function return if you get this far?
    if (s1[i] == s3[k]) {
      // should it return this?
      auto res = dfs(i + 1, j, k + 1);
    }

    // or false?
  };

  /* return? */ dfs(0, 0);
}

In C++23, the feature "Deducing this" P0847 will make it possible to define your lambda as such:

auto dfs = [&](this auto& me, int i, int j, int k) -> bool {
    if (k > s3.length()) return true;
    if (s1[i] == s3[k]) return me(i + 1, j, k + 1);
    return false;
};

edited Sep 7, 2022 at 22:46

answered May 8, 2020 at 12:58

Ted Lyngmo

124k7 gold badges93 silver badges155 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

463035818_is_not_an_ai · Accepted Answer · 2020-05-08 12:44:01Z

4

Some problems not directly related to your question: You are not returning from all paths in the lambda, dfs(0,0) is too little parameters and isInterleave returns nothing. I simply added some return statements without paying attention to the logic.

As mentioned in a comment, you cannot (directly) use the lambda before its type is known. With a level of indirect it can be done:

bool isInterleave(string &s1, string &s2, string &s3) {
  auto dfs = [&](auto F,int i, int j,int k) {
        if (k > s3.length()) {
          return true;
        }
        if (s1[i] == s3[k]) {
            return F(F,i + 1, j, k + 1);     
        }
        else return false;
  };
  return dfs(dfs,0, 0,0);
}

A simpler example to see that this actually works:

#include <iostream>

int main(){ 
    auto recurse = [](auto F,int i,int j){
        if (i == 0) return j;
        return F(F,i-1,j+i);
    };

    std::cout << recurse(recurse,5,0);

}

Output: 15 ( = 5+4+3+2+1+0)

answered May 8, 2020 at 12:44

463035818_is_not_an_ai

129k11 gold badges116 silver badges240 bronze badges

2 Comments

463035818_is_not_an_ai Over a year ago

to be honest I am puzzled how this can possibly work ;)

Ted Lyngmo Over a year ago

When looking at your answer Today, I find it extremely similar to what will actually be added in C++23 as "Deducing this" where your auto F is this auto&. +1

Collectives™ on Stack Overflow

C++2a recursive lambda within a function

2 Answers 2

Comments

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related