Rekursive Lambda-Funktionen in C++11

Lesezeit: 12 Minuten

Rekursive Lambda Funktionen in C11
Weima

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:

[email protected]:~/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?

  • Könnten dies statische vs. implizit dynamische Deklarationen sein?

    – Hamish Grubijan

    14. Januar 2010 um 22:32 Uhr

  • Was ist das mutable Stichwort tut es?

    – Prost und hth. – Alf

    22. Juli 2016 um 0:45 Uhr

  • Das Erfassen von Variablen mit nicht automatischer Speicherdauer ist nicht erlaubt. Sie sollten es so machen: chat.stackoverflow.com/transcript/message/39298544#39298544

    – Euri Pinhollow

    30. September 2017 um 19:53 Uhr

  • Nur zu Ihrer Information, in Ihrem zweiten Code-Snippet ist Ihr Lambda zu ausführlich, berücksichtigen Sie diese Änderung: std::function<int(int,int)> sum = [&](int a, int b) {

    – aalimian

    22. Juli 2020 um 3:08 Uhr


  • Wenn jemand antworten kann, ob die Schwanzrekursionsoptimierung mit einer der Lösungen funktioniert, wäre dies willkommen.

    – Johan Boule

    3. Dezember 2021 um 22:49 Uhr

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.

  • Ich bin damit nicht einverstanden. Der Typ des Lambda ist bekannt, sobald der Funktionskörper eingegeben wird – es gibt keinen Grund, warum er bis dahin nicht abgeleitet werden sollte.

    – Hündchen

    23. Juni 2011 um 12:30 Uhr

  • @DeadMG aber die Spezifikation verbietet es, sich auf die zu beziehen auto Variable im Initialisierer davon. der Typ der Auto-Variablen ist noch nicht bekannt, wenn der Initialisierer verarbeitet wird.

    – Johannes Schaub – litb

    23. Juni 2011 um 17:33 Uhr

  • Sie fragen sich, warum dies nicht als “Antwort” gekennzeichnet ist und dass Python als “Antwort” klassifiziert ist?!

    – Ajay

    26. Januar 2013 um 6:05 Uhr

  • @Puppy: Im Falle einer impliziten Erfassung werden jedoch aus Effizienzgründen nur referenzierte Variablen tatsächlich erfasst, sodass der Körper analysiert werden muss.

    – kec

    4. Dezember 2014 um 23:30 Uhr

  • Gibt es eine gültige Interpretation für sum außer std::function<int(int, int)>oder hat sich die C++-Spezifikation einfach nicht die Mühe gemacht, darauf zu schließen?

    – Mateen Ulhaq

    22. September 2018 um 22:58 Uhr


1646896813 622 Rekursive Lambda Funktionen in C11
Johann Lundberg

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

  • Dies scheint viel schlimmer zu sein, als explizit zu verwenden function<>. Ich kann nicht verstehen, warum jemand es vorziehen würde. Edit: Es ist anscheinend schneller.

    – Timmm

    25. Juli 2018 um 10:29 Uhr


  • Dies ist aus drei Gründen viel besser als std::function: Es erfordert keine Typlöschung oder Speicherzuweisung, es kann constexpr sein und es funktioniert ordnungsgemäß mit automatischen (auf Vorlagen basierenden) Parametern / Rückgabetypen

    – Ivan Sanz Carasa

    12. September 2018 um 8:14 Uhr


  • Vermutlich hat diese Lösung auch den Vorteil, dass sie kopierbar ist, ohne dass die std::function-Referenz den Gültigkeitsbereich verlässt?

    – Uri Granta

    11. Februar 2019 um 11:41 Uhr


  • Hm, beim Versuch hat sich GCC 8.1 (Linux) beschwert: error: use of ‘[...]’ before deduction of ‘auto’ – benötigt, um den Rückgabetyp explizit anzugeben (auf der anderen Seite war keine Änderung erforderlich).

    – Aconcagua

    23. März 2019 um 15:40 Uhr

  • @JohanLundberg Es funktioniert nur, wenn die Funktion eine andere Rückgabe enthält (damit der Rückgabetyp abgeleitet werden kann) – im Beispiel gibt es bereits eine return 0 so kann der Compiler ableiten, dass der Rückgabetyp ist int — im allgemeinen Fall ist die Angabe des Rückgabetyps erforderlich.

    – Benutzer202729

    5. August 2020 um 16:33 Uhr

Rekursive Lambda Funktionen in C11
Barry

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

  • Der Y-Kombinator ist sicherlich der richtige Weg. Aber Sie sollten wirklich ein Nicht-const Überlastung, falls das bereitgestellte Funktionsobjekt eine nicht-const Anruf-Operator. Und verwenden Sie SFINAE und berechnet noexcept für beide. Außerdem wird die Maker-Funktion in C++17 nicht mehr benötigt.

    – Deduplizierer

    25. August 2018 um 21:43 Uhr


  • @minex Ja, auto sum kopiert… aber es kopiert a reference_wrapper, was dasselbe ist wie das Aufnehmen einer Referenz. Wenn Sie dies einmal in der Implementierung tun, bedeutet dies, dass keine der Verwendungen jemals versehentlich kopiert wird.

    – Barri

    22. September 2019 um 1:00 Uhr

  • Ich weiß nicht warum, aber es sieht so aus, als müsste ich hinzufügen ->void Geben Sie Typinformationen an mein Lambda zurück, andernfalls schlägt die Kompilierung fehl: godbolt.org/z/WWj14P

    – qbolec

    2. Januar 2021 um 8:51 Uhr

  • @qbolec Compiler muss wissen, was er zurückgibt, und es gibt keine return um es anzugeben, also muss man es manchmal einfach angeben (auch wenn es in diesem Fall “offensichtlich” sein sollte) void)

    – Barri

    2. Januar 2021 um 15:41 Uhr

  • @Barry, was du sagst, könnte Teil der Geschichte sein, aber es muss noch etwas mehr dahinterstecken, als hinzuzufügen return 42; die Funktion scheint nicht genug – es muss noch -> int : lebend

    – qbolec

    3. Januar 2021 um 16:56 Uhr

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

1646896813 186 Rekursive Lambda Funktionen in C11
Tomilov Anatoliy

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.

  • Die einzige Antwort hier, die tatsächlich nützlich aussieht.

    – Petrus

    9. Februar 2021 um 13:09 Uhr

  • Dies ist eigentlich identisch mit der Übergabe von Lambda selbst als Parameter. Wie können Sie den Beitrag über dem Beitrag von @JohanLundberg nicht lesen?

    – Nick Huang

    27. Januar um 11:16 Uhr


Rekursive Lambda Funktionen in C11
Zuza

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.

  • Die einzige Antwort hier, die tatsächlich nützlich aussieht.

    – Petrus

    9. Februar 2021 um 13:09 Uhr

  • Dies ist eigentlich identisch mit der Übergabe von Lambda selbst als Parameter. Wie können Sie den Beitrag über dem Beitrag von @JohanLundberg nicht lesen?

    – Nick Huang

    27. Januar um 11:16 Uhr


1646896815 823 Rekursive Lambda Funktionen in C11
Entwickler Null

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?).

  • -1. Beachten Sie, dass der einzige Grund, warum die „Lambda“-Version länger dauert, darin besteht, dass Sie sie an eine std::function binden, die den operator()-Aufruf zu einem virtuellen Aufruf macht, und das würde offensichtlich länger dauern. Darüber hinaus hat Ihr Code im Release-Modus von VS2012 in beiden Fällen ungefähr gleich lange gedauert.

    – Yam Marcovic

    27. Februar 2013 um 16:52 Uhr

  • @YamMarcovic Was? Dies ist derzeit die einzige bekannte Möglichkeit, ein rekursives Lambda zu schreiben (das war der Punkt des Beispiels). Ich bin sehr erfreut zu wissen, dass VS2012 einen Weg gefunden hat, diesen Anwendungsfall zu optimieren (obwohl es in letzter Zeit weitere Entwicklungen zu diesem Thema gegeben hat, hätte mein Lambda anscheinend mehr erfasst, wenn es nicht in die std::function small- Speicherfunktoroptimierungen oder so weiter).

    – mmocny

    27. Februar 2013 um 18:46 Uhr

  • Anerkannt. Ich habe deinen Beitrag falsch verstanden. +1 dann. Gah, kann nur positiv abstimmen, wenn Sie diese Antwort bearbeiten. Könnten Sie es also etwas mehr betonen, wie zum Beispiel im Kommentar?

    – Yam Marcovic

    27. Februar 2013 um 19:46 Uhr


  • @YamMarcovic Fertig. Ich schätze Ihre Bereitschaft, Feedback zu geben und es bei Bedarf zu verfeinern. +1 für Sie, guter Herr.

    – mmocny

    27. Februar 2013 um 20:40 Uhr

  • Zeit 0 bedeutet in der Regel “komplette Operation wurde wegoptimiert”. Das Nehmen von Eingaben von cin macht nichts, wenn der Compiler beweist, dass Sie nichts mit dem Ergebnis Ihrer Berechnung tun.

    – Yakk – Adam Nevraumont

    15. März 2017 um 17:39 Uhr

986840cookie-checkRekursive Lambda-Funktionen in C++11

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy