Ich bin neu bei C++11. Ich schreibe die folgende rekursive Lambda-Funktion, aber sie wird nicht kompiliert.

Summe.cpp

#include <iostream>
#include <functional>

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

Kompilierungsfehler:

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

sum.cpp: In Lambda-Funktion: sum.cpp:18:36: error: ‘((<lambda(int, int)>*)this)-><lambda(int, int)>::sum‘ kann nicht als Funktion verwendet werden

gcc-Version

gcc-Version 4.5.0 20091231 (experimentell) (gcc)

Aber wenn ich die Erklärung von ändere sum() wie unten, es funktioniert:

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

Könnte bitte jemand Licht ins Dunkel bringen?

Denken Sie an den Unterschied zw Auto Version und die vollständig spezifizierte Typversion. Die Auto Schlüsselwort leitet seinen Typ von dem ab, womit es initialisiert wurde, aber was Sie initialisieren, muss wissen, was sein Typ ist (in diesem Fall muss die Lambda-Closure die Typen kennen, die sie erfasst). Irgendwie ein Henne-Ei-Problem.

Andererseits muss der Typ eines vollständig spezifizierten Funktionsobjekts nichts darüber „wissen“, was ihm zugewiesen wird, und daher kann die Closure des Lambdas ebenfalls vollständig über die Typen informiert werden, die es erfasst.

Betrachten Sie diese geringfügige Änderung Ihres Codes und es kann sinnvoller sein:

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

Offensichtlich würde dies nicht mit funktionieren Auto. Rekursive Lambda-Funktionen funktionieren perfekt (zumindest in MSVC, wo ich Erfahrung mit ihnen habe), es ist nur so, dass sie nicht wirklich mit der Typinferenz kompatibel sind.

Der Trick besteht darin, die Lambda-Implementierung in sich selbst einzuspeisen als Parameternicht durch Gefangennahme.

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

Alle Probleme in der Informatik können durch eine andere Indirektionsebene gelöst werden. Ich fand diesen einfachen Trick zuerst bei http://pedromendez.com/blog/2015/07/16/recursive-lambdas-in-c14/

Es tut erfordern C ++ 14, während die Frage auf C ++ 11 lautet, aber vielleicht für die meisten interessant ist.

Übergehen std::function ist aber auch möglich kann führt zu langsamerem Code. Aber nicht immer. Sehen Sie sich die Antworten auf std::function vs. template an

Dies ist nicht nur eine Besonderheit von C++, sondern entspricht direkt der Mathematik des Lambda-Kalküls. Von Wikipedia:

Lambda calculus cannot express this as directly as some other notations:
all functions are anonymous in lambda calculus, so we can't refer to a
value which is yet to be defined, inside the lambda term defining that
same value. However, recursion can still be achieved by arranging for a
lambda expression to receive itself as its argument value

Mit C++14 ist es jetzt ganz einfach, ein effizientes rekursives Lambda zu erstellen, ohne den zusätzlichen Overhead von verursachen zu müssen std::functionin nur wenigen Codezeilen:

template <class F>
struct y_combinator {
    F f; // the lambda will be stored here
    
    // a forwarding operator():
    template <class... Args>
    decltype(auto) operator()(Args&&... args) const {
        // we pass ourselves to f, then the arguments.
        return f(*this, std::forward<Args>(args)...);
    }
};

// helper function that deduces the type of the lambda:
template <class F>
y_combinator<std::decay_t<F>> make_y_combinator(F&& f) {
    return {std::forward<F>(f)};
}

mit dem Ihr Original sum Versuch wird:

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

In C++17 können wir mit CTAD einen Abzugsleitfaden hinzufügen:

template <class F> y_combinator(F) -> y_combinator<F>;

Was die Hilfsfunktion überflüssig macht. Wir können einfach schreiben y_combinator{[](auto self, ...){...}} direkt.

In C++20 mit CTAD für Aggregate ist der Abzugsleitfaden nicht erforderlich.

In C ++ 23 benötigen Sie mit dieser Ableitung überhaupt keinen Y-Kombinator:

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

Ich habe eine andere Lösung, arbeite aber nur mit zustandslosen Lambdas:

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

Der Trick dabei ist, dass Lambdas auf statische Variablen zugreifen können und Sie zustandslose in Funktionszeiger konvertieren können.

Sie können es mit Standard-Lambdas verwenden:

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

Seine Arbeit in GCC 4.7

Um Lambda rekursiv zu machen, ohne externe Klassen und Funktionen (wie std::function oder Festkomma-Kombinator) kann man in C++14 folgende Konstruktion verwenden (Live-Beispiel):

#include <utility>
#include <list>
#include <memory>
#include <iostream>

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

Drucke:

1
 2
  8
 3
  5
   7
  6
 4

Beachten Sie, dass der Ergebnistyp von Lambda explizit angegeben werden sollte.

Sie kann Lassen Sie eine Lambda-Funktion sich selbst rekursiv aufrufen. Das Einzige, was Sie tun müssen, ist, es über einen Funktionswrapper zu referenzieren, damit der Compiler seinen Rückgabe- und Argumenttyp kennt (Sie können keine Variable erfassen – das Lambda selbst – das noch nicht definiert wurde). .

  function<int (int)> f;

  f = [&f](int x) {
    if (x == 0) return 0;
    return x + f(x-1);
  };

  printf("%d\n", f(10));

Achten Sie sehr darauf, den Geltungsbereich des Wrappers f nicht zu überschreiten.

Ich habe einen Benchmark durchgeführt, bei dem eine rekursive Funktion mit einer rekursiven Lambda-Funktion verglichen wurde std::function<> Erfassungsmethode. Bei vollständig aktivierten Optimierungen in der Clang-Version 4.1 lief die Lambda-Version deutlich langsamer.

#include <iostream>
#include <functional>
#include <chrono>

uint64_t sum1(int n) {
  return (n <= 1) ? 1 : n + sum1(n - 1);
}

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

auto const ITERATIONS = 10000;
auto const DEPTH = 100000;

template <class Func, class Input>
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<std::chrono::milliseconds>(t2-t1).count();
  std::cout << "Duration: " << duration << std::endl;
}

int main() {
  benchmark(sum1, DEPTH);
  benchmark(sum2, DEPTH);
}

Erzeugt Ergebnisse:

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

(Hinweis: Ich habe auch mit einer Version bestätigt, die die Eingaben von cin übernommen hat, um die Auswertung der Kompilierzeit zu eliminieren.)

Clang erzeugt auch eine Compiler-Warnung:

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

Was erwartet und sicher ist, aber beachtet werden sollte.

Es ist großartig, eine Lösung in unseren Toolbelts zu haben, aber ich denke, die Sprache braucht einen besseren Weg, um diesen Fall zu handhaben, wenn die Leistung mit aktuellen Methoden vergleichbar sein soll.

Notiz:

Wie ein Kommentator betonte, scheint die neueste Version von VC++ einen Weg gefunden zu haben, dies bis zu dem Punkt gleicher Leistung zu optimieren. Vielleicht brauchen wir doch keinen besseren Weg, damit umzugehen (außer syntaktischem Zucker).

Auch, wie einige andere SO-Posts in den letzten Wochen skizziert haben, die Leistung von std::function<> selbst kann die Ursache für die Verlangsamung gegenüber dem direkten Aufruf der Funktion sein, zumindest wenn die Lambda-Erfassung zu groß ist, um in einen bibliotheksoptimierten Bereich zu passen std::function verwendet für kleine Funktoren (ich denke, so etwas wie die verschiedenen kurzen String-Optimierungen?).