Funzioni lambda ricorsive in C ++ 11

Sono nuovo di C ++ 11. Sto scrivendo la seguente funzione lambda ricorsiva, ma non viene compilata.

sum.cpp

#include  #include  auto term = [](int a)->int { return a*a; }; auto next = [](int a)->int { return ++a; }; auto sum = [term,next,&sum](int a, int b)mutable ->int { if(a>b) return 0; else return term(a) + sum(next(a),b); }; int main(){ std::cout<<sum(1,10)<<std::endl; return 0; } 

errore di compilazione:

vimal @ linux-718q: ~ / Study / 09C ++ / c ++ 0x / lambda> g ++ -std = c ++ 0x sum.cpp

sum.cpp: Nella funzione lambda: sum.cpp: 18: 36: error: ‘ ((*)this)->::sum ‘ non può essere utilizzato come una funzione

versione gcc

gcc versione 4.5.0 20091231 (sperimentale) (GCC)

Ma se cambio la dichiarazione di sum() come sotto, funziona:

 std::function sum = [term,next,&sum](int a, int b)->int { if(a>b) return 0; else return term(a) + sum(next(a),b); }; 

Qualcuno potrebbe far luce su questo?

Pensa alla differenza tra la versione automatica e la versione del tipo completamente specificato. La parola chiave auto deduce il suo tipo da qualsiasi inizializzazione, ma ciò che stai inizializzando con deve sapere qual è il suo tipo (in questo caso, la chiusura lambda deve conoscere i tipi che sta catturando). Qualcosa di un problema di pollo e uova.

D’altra parte, un tipo di object funzione completamente specificato non ha bisogno di “sapere” nulla su ciò che gli viene assegnato, e così anche la chiusura di lambda può essere pienamente informata sui tipi che cattura.

Considera questa leggera modifica del tuo codice e potrebbe avere più senso:

 std::function sum; sum = [term,next,&sum](int a, int b)->int { if(a>b) return 0; else return term(a) + sum(next(a),b); }; 

Ovviamente, questo non funzionerebbe con l’ auto . Le funzioni lambda ricorsive funzionano perfettamente (almeno lo fanno in MSVC, dove ho esperienza con loro), è solo che non sono realmente compatibili con l’inferenza di tipo.

Il trucco è di alimentare l’implementazione lambda a se stessa come parametro , non per cattura.

 const auto sum = [term,next](int a, int b) { auto sum_impl=[term,next](int a,int b,auto& sum_ref) mutable { if(a>b){ return 0; } return term(a) + sum_ref(next(a),b,sum_ref); }; return sum_impl(a,b,sum_impl); }; 

Tutti i problemi in informatica possono essere risolti da un altro livello di riferimento indiretto . Ho trovato per la prima volta questo facile trucco su http://pedromelendez.com/recursive-lambdas-in-c14/

Richiede C ++ 14 mentre la domanda è su C ++ 11, ma forse interessante per la maggior parte.

Passare tramite std::function è anche ansible ma può comportare un codice più lento. Ma non sempre. Dai un’occhiata alle risposte a std :: function vs template

Ho un’altra soluzione, ma lavoro solo con lambda senza stato:

 void f() { static int (*self)(int) = [](int i)->int { return i>0 ? self(i-1)*i : 1; }; std::cout<  

Il trucco qui è che lambdas può accedere a variabili statiche ed è ansible convertire quelle senza stato al puntatore a funzione.

Puoi usarlo con lambda standard:

 void g() { int sum; auto rec = [&sum](int i) -> int { static int (*inner)(int&, int) = [](int& _sum, int i)->int { _sum += i; return i>0 ? inner(_sum, i-1)*i : 1; }; return inner(sum, i); }; } 

Il suo lavoro in GCC 4.7

Con C ++ 14, ora è abbastanza facile creare un lambda ricorsivo efficiente senza dover sostenere l’overhead aggiuntivo di std::function , in poche righe di codice (con una piccola modifica dell’originale per impedire all’utente di prendendo una copia accidentale):

 template  struct y_combinator { F f; // the lambda will be stored here // a forwarding operator(): template  decltype(auto) operator()(Args&&... args) const { // we pass ourselves to f, then the arguments. // [edit: Barry] pass in std::ref(*this) instead of *this return f(std::ref(*this), std::forward(args)...); } }; // helper function that deduces the type of the lambda: template  y_combinator> make_y_combinator(F&& f) { return {std::forward(f)}; } 

con il quale il tuo tentativo di sum originale diventa:

 auto sum = make_y_combinator([term,next](auto sum, int a, int b) { if (a>b) { return 0; } else { return term(a) + sum(next(a),b); } }); 

È ansible effettuare una chiamata a funzione lambda in modo ricorsivo. L’unica cosa che devi fare è fare riferimento ad esso attraverso un wrapper di funzioni in modo che il compilatore sappia che è di tipo return e argument (non puoi catturare una variabile – la stessa lambda – che non è stata ancora definita) .

  function f; f = [&f](int x) { if (x == 0) return 0; return x + f(x-1); }; printf("%d\n", f(10)); 

State molto attenti a non esaurire l’ambito del wrapper f.

Per fare ricapitolare lambda senza usare classi e funzioni esterne (come std::function o combinatore a virgola fissa) si può usare la seguente costruzione in C ++ 14 ( esempio dal vivo ):

 #include  #include  #include  #include  int main() { struct tree { int payload; std::list< tree > children = {}; // std::list of incomplete type is allowed }; std::size_t indent = 0; // indication of result type here is essential const auto print = [&] (const auto & self, const tree & node) -> void { std::cout < < std::string(indent, ' ') << node.payload << '\n'; ++indent; for (const tree & t : node.children) { self(self, t); } --indent; }; print(print, {1, {{2, {{8}}}, {3, {{5, {{7}}}, {6}}}, {4}}}); } 

stampe:

 1 2 8 3 5 7 6 4 

Nota, il tipo di risultato di lambda deve essere specificato esplicitamente.

Ho eseguito un benchmark confrontando una funzione ricorsiva con una funzione lambda ricorsiva usando il metodo di cattura std::function<> . Con le ottimizzazioni ottimizzate abilitate su clang versione 4.1, la versione lambda ha funzionato molto più lentamente.

 #include  #include  #include  uint64_t sum1(int n) { return (n < = 1) ? 1 : n + sum1(n - 1); } std::function sum2 = [&] (int n) { return (n < = 1) ? 1 : n + sum2(n - 1); }; auto const ITERATIONS = 10000; auto const DEPTH = 100000; template  void benchmark(Func&& func, Input&& input) { auto t1 = std::chrono::high_resolution_clock::now(); for (auto i = 0; i != ITERATIONS; ++i) { func(input); } auto t2 = std::chrono::high_resolution_clock::now(); auto duration = std::chrono::duration_cast(t2-t1).count(); std::cout < < "Duration: " << duration << std::endl; } int main() { benchmark(sum1, DEPTH); benchmark(sum2, DEPTH); } 

Produce risultati:

 Duration: 0 // regular function Duration: 4027 // lambda function 

(Nota: ho anche confermato con una versione che ha preso gli input da cin, in modo da eliminare la valutazione del tempo di compilazione)

Clang produce anche un avvertimento sul compilatore:

 main.cc:10:29: warning: variable 'sum2' is uninitialized when used within its own initialization [-Wuninitialized] 

Quale è previsto e sicuro, ma dovrebbe essere notato.

È bello avere una soluzione nei nostri toolbar, ma penso che il linguaggio avrà bisogno di un modo migliore per gestire questo caso se le prestazioni devono essere paragonabili ai metodi attuali.

Nota:

Come ha fatto notare un commentatore, sembra che l'ultima versione di VC ++ abbia trovato un modo per ottimizzarlo al punto di eguali prestazioni. Forse non abbiamo bisogno di un modo migliore per gestire questo, dopo tutto (tranne che per lo zucchero sintattico).

Inoltre, come alcuni altri post di SO hanno delineato nelle ultime settimane, le prestazioni di std::function<> possono essere la causa della funzione di rallentamento o di chiamata direttamente, almeno quando l'acquisizione lambda è troppo grande per adattarsi ad alcune librerie ottimizzate spazio std::function utilizza per piccoli-funtori (immagino come le varie ottimizzazioni di stringa breve?).

Questa è un’implementazione leggermente più semplice dell’operatore del fixpoint che rende un po ‘più ovvio esattamente quello che sta succedendo.

 #include  #include  using namespace std; template struct fixpoint { typedef function effective_type; typedef function function_type; function_type f_nonr; T operator()(Args... args) const { return f_nonr(*this, args...); } fixpoint(const function_type& p_f) : f_nonr(p_f) { } }; int main() { auto fib_nonr = [](const function& f, int n) -> int { return n < 2 ? n : f(n-1) + f(n-2); }; auto fib = fixpoint(fib_nonr); for (int i = 0; i < 6; ++i) { cout << fib(i) << '\n'; } } 

C ++ 14: Ecco un set generico di lambda anonimo ricorsivo / senza cattura generico che emette tutti i numeri da 1, 20

 ([](auto f, auto n, auto m) { f(f, n, m); })( [](auto f, auto n, auto m) -> void { cout < < typeid(n).name() << el; cout << n << el; if (n 

Se capisco correttamente questo sta usando la soluzione Y-combinator

E qui è la sum (n, m) versione

 auto sum = [](auto n, auto m) { return ([](auto f, auto n, auto m) { int res = f(f, n, m); return res; })( [](auto f, auto n, auto m) -> int { if (n > m) return 0; else { int sum = n + f(f, n + 1, m); return sum; } }, n, m); }; auto result = sum(1, 10); //result == 55 

Stai cercando di catturare una variabile (sum) che stai definendo. Non può essere buono.

Non penso che siano possibili lambda autenticamente C ++ 0x. Dovresti essere in grado di catturare altri lambda, però.

Ecco la risposta finale per l’OP. Ad ogni modo, Visual Studio 2010 non supporta l’acquisizione di variabili globali. E non è necessario catturarli perché la variabile globale è accessibile a livello globale mediante la definizione. La risposta seguente utilizza invece la variabile locale.

 #include  #include  template struct t2t { typedef T t; }; template struct fixpoint { typedef std::function func_t; typedef std::function tfunc_t; typedef std::function yfunc_t; class loopfunc_t { public: func_t operator()(loopfunc_t v)const { return func(v); } template loopfunc_t(const L &l):func(l){} typedef V1 Parameter1_t; typedef V2 Parameter2_t; private: std::function func; }; static yfunc_t fix; }; template typename fixpoint::yfunc_t fixpoint::fix = [](tfunc_t f) -> func_t { return [f](fixpoint::loopfunc_t x){ return f(x(x)); } ([f](fixpoint::loopfunc_t x) -> fixpoint::func_t{ auto &ff = f; return [ff, x](t2t::t::Parameter1_t v1, t2t::t::Parameter1_t v2){ return ff(x(x))(v1, v2); }; }); }; int _tmain(int argc, _TCHAR* argv[]) { auto term = [](int a)->int { return a*a; }; auto next = [](int a)->int { return ++a; }; auto sum = fixpoint::fix( [term,next](std::function sum1) -> std::function{ auto &term1 = term; auto &next1 = next; return [term1, next1, sum1](int a, int b)mutable ->int { if(a>b) return 0; else return term1(a) + sum1(next1(a),b); }; }); std::cout<  

Hai bisogno di un combinatore a virgola fissa. Vedi questo .

o guarda il seguente codice:

 //As decltype(variable)::member_name is invalid currently, //the following template is a workaround. //Usage: t2t::t::member_name template struct t2t { typedef T t; }; template struct fixpoint { typedef std::function func_t; typedef std::function tfunc_t; typedef std::function yfunc_t; class loopfunc_t { public: func_t operator()(loopfunc_t v)const { return func(v); } template loopfunc_t(const L &l):func(l){} typedef V Parameter_t; private: std::function func; }; static yfunc_t fix; }; template typename fixpoint::yfunc_t fixpoint::fix = [](fixpoint::tfunc_t f) -> fixpoint::func_t { fixpoint::loopfunc_t l = [f](fixpoint::loopfunc_t x) -> fixpoint::func_t{ //f cannot be captured since it is not a local variable //of this scope. We need a new reference to it. auto &ff = f; //We need struct t2t because template parameter //V is not accessable in this level. return [ff, x](t2t::t::Parameter_t v){ return ff(x(x))(v); }; }; return l(l); }; int _tmain(int argc, _TCHAR* argv[]) { int v = 0; std::function fac = fixpoint::fix([](std::function f) -> std::function{ return [f](int i) -> int{ if(i==0) return 1; else return i * f(i-1); }; }); int i = fac(10); std::cout < < i; //3628800 return 0; } 

Questa risposta è inferiore a quella di Yankes, ma ancora, ecco qui:

 using dp_type = void (*)(); using fp_type = void (*)(dp_type, unsigned, unsigned); fp_type fp = [](dp_type dp, unsigned const a, unsigned const b) { ::std::cout < < a << ::std::endl; return reinterpret_cast(dp)(dp, b, a + b); }; fp(reinterpret_cast(fp), 0, 1);