C ++ 2a рекурсивная лямбда внутри функции

Question

Я пытаюсь скомпилировать это:

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

Я получаю сообщение об ошибке:

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

      | ^

Как мне это исправить?

Answer 1

'dfs', объявленный с выведенным типом 'auto', не может отображаться в его собственном инициализаторе

С рекурсивными лямбдами вы можете использовать std::function для предоставления подписи, поэтому у него нет выводится:

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

Answer 2

Некоторые проблемы, не связанные напрямую с вашим вопросом: вы не возвращаетесь со всех путей в лямбда-выражении, dfs(0,0) слишком мало параметров и isInterleave ничего не возвращает. Я просто добавил несколько операторов return, не обращая внимания на лог c.

Как упоминалось в комментарии, вы не можете (напрямую) использовать лямбду, пока не известен ее тип. С косвенным уровнем это можно сделать:

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

Более простой пример, чтобы увидеть, что это действительно работает:

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

}

Вывод: 15 (= 5 + 4 + 3 + 2 + 1 + 0)