wake-up-neo.com

Rekursive Lambda-Funktionen in C++ 11

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

sum.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 der Lambda-Funktion: sum.cpp: 18: 36: Fehler: ((<lambda(int, int)>*)this)-><lambda(int, int)>::sum kann nicht als Funktion verwendet werden

gcc version

gcc Version 4.5.0 20091231 (experimentell) (GCC)

Wenn ich jedoch die Deklaration von sum() wie folgt ändere, funktioniert es:

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 jemand bitte Licht auf dieses werfen?

106
weima

Denken Sie über den Unterschied zwischen der auto -Version und der vollständig angegebenen Typversion nach. Das Schlüsselwort auto leitet seinen Typ von dem zurück, mit dem es initialisiert wurde, aber was Sie mit dem Initialisieren initialisieren, muss wissen, um welchen Typ es sich handelt (in diesem Fall muss der Lambda-Verschluss wissen, welche Typen er erfassen). So etwas wie ein Henne-und-Ei-Problem.

Auf der anderen Seite muss der Typ eines vollständig spezifizierten Funktionsobjekts nicht wissen, was ihm zugewiesen wird. Daher kann auch die Schließung des Lambda vollständig über die Typen informiert werden, die er 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 funktioniert das nicht mit auto . Rekursive Lambda-Funktionen funktionieren einwandfrei (zumindest in MSVC, wo ich Erfahrung mit ihnen habe), sie sind einfach nicht mit Typinferenz kompatibel.

137
I. M. McIntosh

Der Trick besteht darin, die Lambda-Implementierung als Parameter einzugeben, nicht durch Capture.

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 zum ersten Mal unter http://pedromelendez.com/recursive-lambdas-in-c14/

It benötigt C++ 14, während sich die Frage auf C++ 11 bezieht, aber für die meisten vielleicht interessant.

Es ist auch möglich, über std::function zu gehen, aber kann zu langsamerem Code führen. Aber nicht immer. Schauen Sie sich die Antworten zu std :: function vs template an

38
Johan Lundberg

Mit C++ 14 ist es jetzt recht einfach, ein effizientes rekursives Lambda zu erstellen, ohne den zusätzlichen Aufwand von std::function in nur wenigen Codezeilen aufbringen zu müssen (mit einer kleinen Änderung des Originals, um zu verhindern, dass der Benutzer versehentlich reagiert Kopieren):

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.
        // [edit: Barry] pass in std::ref(*this) instead of *this
        return f(std::ref(*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 ursprünglicher sum-Versuch wird:

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

Ich habe eine andere Lösung, arbeite aber nur mit staatenlosen 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 stateless zu 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

20
Yankes

Sie can lassen eine Lambda-Funktion sich selbst rekursiv aufrufen. Das einzige, was Sie tun müssen, ist, über einen Wrapper für Funktionen darauf zu verweisen, damit der Compiler den Rückgabewert und den Argumenttyp erkennt (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 darauf, dass Sie nicht den Bereich des Wrappers verlassen. F.

10
Zuza

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

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

druckt:

1
 2
  8
 3
  5
   7
  6
 4

Der Ergebnistyp von Lambda sollte explizit angegeben werden.

8
Orient

Ich habe einen Benchmarkvergleich durchgeführt, bei dem eine rekursive Funktion mit einer rekursiven Lambda-Funktion verglichen wurde, wobei die std::function<>-Capture-Methode verwendet wurde. Da in clang Version 4.1 vollständige Optimierungen aktiviert waren, lief die Lambda-Version erheblich 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);
}

Produziert 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 vermeiden.)

Clang gibt auch eine Compiler-Warnung aus:

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

Welches erwartet und sicher ist, sollte aber beachtet werden.

Es ist großartig, eine Lösung in unseren Toolbelts zu haben, aber ich denke, die Sprache wird einen besseren Weg benötigen, um mit diesem Fall umzugehen, wenn die Leistung mit den derzeitigen Methoden vergleichbar sein soll.

Hinweis:

Wie ein Kommentator feststellte, scheint die neueste Version von VC++ einen Weg gefunden zu haben, dies auf die gleiche Leistung hin zu optimieren. Vielleicht brauchen wir doch keinen besseren Weg, um damit umzugehen (außer bei syntaktischem Zucker).

Wie einige andere SO -Postings in den letzten Wochen bereits skizziert haben, kann die Leistung von std::function<> selbst die Ursache für die Verlangsamung der Funktion direkt sein, zumindest wenn die Lambda-Capture zu groß ist, um in einen bibliotheksoptimierten Platz zu passen std::function verwendet für kleine Funktoren (ich schätze, irgendwie mögen die verschiedenen kurzen String-Optimierungen?).

6
mmocny

Dies ist eine etwas einfachere Implementierung des Fixpoint-Operators, was es etwas offensichtlicher macht, was genau passiert.

#include <iostream>
#include <functional>

using namespace std;

template<typename T, typename... Args>
struct fixpoint
{
    typedef function<T(Args...)> effective_type;
    typedef function<T(const effective_type&, Args...)> 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<int(int)>& f, int n) -> int
    {
        return n < 2 ? n : f(n-1) + f(n-2);
    };

    auto fib = fixpoint<int,int>(fib_nonr);

    for (int i = 0; i < 6; ++i)
    {
        cout << fib(i) << '\n';
    }
}
1
Pseudonym

C++ 14: Hier ist eine rekursive anonyme Stateless/No-Capture-Gruppe von Lambdas Die alle Zahlen von 1, 20 ausgibt

([](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<m)
        f(f, ++n, m);
},
    1, 20);

Wenn ich es richtig verstanden habe, benutze ich die Y-Kombinatorlösung

Und hier ist die Summenversion (n, m)

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
0
Jonas Brandel