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)

Aber wenn ich die Erklärung 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 ins Dunkel bringen?

Denken Sie an den Unterschied zwischen der automatischen Version und der vollständig angegebenen Typversion. Das Auto- Schlüsselwort leitet seinen Typ von dem ab, mit dem es initialisiert wurde, aber was Sie damit initialisieren, muss wissen, um welchen Typ es sich handelt (in diesem Fall muss der Lambda-Abschluss die Typen kennen, die erfasst werden). So etwas wie ein Henne-Ei-Problem.

Andererseits muss der Typ eines vollständig spezifizierten Funktionsobjekts nichts darüber "wissen", was ihm zugewiesen wird, und so kann der Abschluss des Lambdas ebenfalls 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 würde dies mit Auto nicht funktionieren . Rekursive Lambda-Funktionen funktionieren einwandfrei (zumindest in MSVC, wo ich Erfahrung mit ihnen habe), nur dass sie nicht wirklich mit Typinferenz kompatibel sind.

Der Trick besteht darin, die Lambda-Implementierung als Parameter und nicht durch Erfassung in sich selbst einzugeben.

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 habe diesen einfachen Trick zuerst bei gefunden http://pedromelendez.com/blog/2015/07/16/recursive-lambdas-in-c14/ gefunden.

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

Das Durchgehen std::functionist ebenfalls möglich, kann jedoch zu einem langsameren Code führen. Aber nicht immer. Schauen Sie sich die Antworten auf std :: function vs template an

Dies ist nicht nur eine Besonderheit von C ++, sondern eine direkte Abbildung auf die Mathematik der Lambda-Rechnung. Aus 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 std::functionin nur wenigen Codezeilen zu erstellen, ohne den zusätzlichen Aufwand dafür zu verursachen (mit einer kleinen Bearbeitung des Originals, um zu verhindern, dass der Benutzer versehentlich eine Kopie erstellt ):

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

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

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

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

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

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

Sie können eine Lambda-Funktion selbst rekursiv aufrufen lassen. Das einzige, was Sie tun müssen, ist, es über einen Funktions-Wrapper zu referenzieren, damit der Compiler den Rückgabe- und Argumenttyp kennt (Sie können keine Variable - das Lambda selbst - erfassen, die 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 Ihnen der Umfang des Wrappers nicht ausgeht. F.

Um Lambda ohne Verwendung externer Klassen und Funktionen (wie std::functionoder Festkomma-Kombinator) rekursiv zu machen, kann in C ++ 14 die folgende Konstruktion verwendet werden ( 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 des Lambda explizit angegeben werden sollte.

Ich habe einen Benchmark durchgeführt, bei dem eine rekursive Funktion mit einer rekursiven Lambda-Funktion unter Verwendung der std::function<>Erfassungsmethode verglichen wurde . Mit vollständigen Optimierungen in 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 Kompilierungszeit zu vermeiden.)

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, 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 brauchen, um diesen Fall zu behandeln, wenn die Leistung mit den aktuellen Methoden vergleichbar sein soll.

Hinweis:

Wie ein Kommentator betonte, scheint die neueste Version von VC ++ einen Weg gefunden zu haben, dies bis zur gleichen Leistung zu optimieren. Vielleicht brauchen wir doch keinen besseren Weg, um damit umzugehen (außer für syntaktischen Zucker).

Wie einige andere SO-Beiträge in den letzten Wochen dargelegt haben, kann die Leistung std::function<>selbst die Ursache für die Verlangsamung gegenüber der direkten Aufruffunktion sein, zumindest wenn die Lambda-Erfassung zu groß ist, um in einige bibliotheksoptimierte Raumnutzungen std::functionfür kleine Funktoren zu passen (Ich denke, irgendwie mögen die verschiedenen Optimierungen für kurze Zeichenfolgen?).

Dies ist eine etwas einfachere Implementierung des Fixpoint-Operators, die es etwas offensichtlicher macht, was genau vor sich geht.

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

Hier ist eine verfeinerte Version der Y-Kombinator-Lösung, die auf einer von @Barry vorgeschlagenen basiert.

template <class F>
struct recursive {
  F f;
  template <class... Ts>
  decltype(auto) operator()(Ts&&... ts)  const { return f(std::ref(*this), std::forward<Ts>(ts)...); }

  template <class... Ts>
  decltype(auto) operator()(Ts&&... ts)  { return f(std::ref(*this), std::forward<Ts>(ts)...); }
};

template <class F> recursive(F) -> recursive<F>;
auto const rec = [](auto f){ return recursive{std::move(f)}; };

Um dies zu verwenden, könnte man Folgendes tun

auto fib = rec([&](auto&& fib, int i) {
// implementation detail omitted.
});

Es ähnelt dem let recSchlüsselwort in OCaml, ist jedoch nicht dasselbe.

C ++ 14: Hier ist ein rekursiver anonymer Satz von Lambdas ohne Status ohne Status, der 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 das richtig verstehe, wird die Y-Kombinator-Lösung verwendet

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

Hier ist die endgültige Antwort für das OP. Visual Studio 2010 unterstützt jedoch nicht die Erfassung globaler Variablen. Und Sie müssen sie nicht erfassen, da auf globale Variablen durch Definieren global zugegriffen werden kann. Die folgende Antwort verwendet stattdessen eine lokale Variable.

#include <functional>
#include <iostream>

template<typename T>
struct t2t
{
    typedef T t;
};

template<typename R, typename V1, typename V2>
struct fixpoint
{
    typedef std::function<R (V1, V2)> func_t;
    typedef std::function<func_t (func_t)> tfunc_t;
    typedef std::function<func_t (tfunc_t)> yfunc_t;

    class loopfunc_t {
    public:
        func_t operator()(loopfunc_t v)const {
            return func(v);
        }
        template<typename L>
        loopfunc_t(const L &l):func(l){}
        typedef V1 Parameter1_t;
        typedef V2 Parameter2_t;
    private:
        std::function<func_t (loopfunc_t)> func;
    };
    static yfunc_t fix;
};
template<typename R, typename V1, typename V2>
typename fixpoint<R, V1, V2>::yfunc_t fixpoint<R, V1, V2>::fix = [](tfunc_t f) -> func_t {
    return [f](fixpoint<R, V1, V2>::loopfunc_t x){  return f(x(x)); }
    ([f](fixpoint<R, V1, V2>::loopfunc_t x) -> fixpoint<R, V1, V2>::func_t{
        auto &ff = f;
        return [ff, x](t2t<decltype(x)>::t::Parameter1_t v1, 
            t2t<decltype(x)>::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<int, int, int>::fix(
    [term,next](std::function<int (int, int)> sum1) -> std::function<int (int, int)>{
        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<<sum(1,10)<<std::endl; //385

    return 0;
}

Sie versuchen, eine Variable (Summe) zu erfassen, die Sie gerade definieren. Das kann nicht gut sein.

Ich denke nicht, dass wirklich selbstrekursive C ++ 0x-Lambdas möglich sind. Sie sollten jedoch in der Lage sein, andere Lambdas zu fangen.

Diese Antwort ist der von Yankes unterlegen, aber hier geht es weiter:

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<fp_type>(dp)(dp, b, a + b);
};

fp(reinterpret_cast<dp_type>(fp), 0, 1);

Sie benötigen einen Festkomma-Kombinator. Sehen Sie das .

oder schauen Sie sich den folgenden Code an:

//As decltype(variable)::member_name is invalid currently, 
//the following template is a workaround.
//Usage: t2t<decltype(variable)>::t::member_name
template<typename T>
struct t2t
{
    typedef T t;
};

template<typename R, typename V>
struct fixpoint
{
    typedef std::function<R (V)> func_t;
    typedef std::function<func_t (func_t)> tfunc_t;
    typedef std::function<func_t (tfunc_t)> yfunc_t;

    class loopfunc_t {
    public:
        func_t operator()(loopfunc_t v)const {
            return func(v);
        }
        template<typename L>
        loopfunc_t(const L &l):func(l){}
        typedef V Parameter_t;
    private:
        std::function<func_t (loopfunc_t)> func;
    };
    static yfunc_t fix;
};
template<typename R, typename V>
typename fixpoint<R, V>::yfunc_t fixpoint<R, V>::fix = 
[](fixpoint<R, V>::tfunc_t f) -> fixpoint<R, V>::func_t {
    fixpoint<R, V>::loopfunc_t l = [f](fixpoint<R, V>::loopfunc_t x) ->
        fixpoint<R, V>::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<decltype(x)>::t::Parameter_t v){
                return ff(x(x))(v); 
            };
        }; 
        return l(l);
    };

int _tmain(int argc, _TCHAR* argv[])
{
    int v = 0;
    std::function<int (int)> fac = 
    fixpoint<int, int>::fix([](std::function<int (int)> f)
        -> std::function<int (int)>{
        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;
}