Je suis nouveau sur C ++ 11. J'écris la fonction lambda récursive suivante, mais elle ne se compile pas.

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

erreur de compilation:

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

sum.cpp: Dans la fonction lambda: sum.cpp: 18: 36: erreur: ' ((<lambda(int, int)>*)this)-><lambda(int, int)>::sum' ne peut pas être utilisé comme fonction

version gcc

gcc version 4.5.0 20091231 (expérimental) (GCC)

Mais si je change la déclaration de sum()comme ci-dessous, cela fonctionne:

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

Quelqu'un pourrait-il s'il vous plaît jeter la lumière là-dessus?

Pensez à la différence entre la version automatique et la version de type entièrement spécifiée. Le mot clé auto déduit son type de tout ce avec quoi il est initialisé, mais ce avec quoi vous l'initialisez doit savoir quel est son type (dans ce cas, la fermeture lambda doit connaître les types qu'elle capture). Quelque chose d'un problème de poule et d'oeuf.

D'un autre côté, le type d'un objet fonction entièrement spécifié n'a pas besoin de "savoir" quoi que ce soit sur ce qui lui est assigné, et ainsi la fermeture du lambda peut également être pleinement informée des types qu'il capture.

Considérez cette légère modification de votre code et cela peut avoir plus de sens:

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

De toute évidence, cela ne fonctionnerait pas avec l' automobile . Les fonctions lambda récursives fonctionnent parfaitement bien (du moins elles le font dans MSVC, où j'ai de l'expérience avec elles), c'est juste qu'elles ne sont pas vraiment compatibles avec l'inférence de type.

L'astuce consiste à alimenter l'implémentation lambda en tant que paramètre , et non par 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);
};

Tous les problèmes en informatique peuvent être résolus par un autre niveau d'indirection . J'ai trouvé cette astuce pour la première fois sur http://pedromelendez.com/blog/2015/07/16/recursive-lambdas-in-c14/

Il ne nécessite C ++ 14 alors que la question est en C ++ 11, mais peut - être intéressant pour la plupart.

Passer via std::functionest également possible, mais peut entraîner un code plus lent. Mais pas toujours. Jetez un œil aux réponses à std :: function vs template

Ce n'est pas seulement une particularité du C ++, c'est un mappage direct avec les mathématiques du calcul lambda. De 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

Avec C ++ 14, il est maintenant assez facile de faire un lambda récursif efficace sans avoir à subir la surcharge supplémentaire de std::function, en seulement quelques lignes de code (avec une petite modification de l'original pour empêcher l'utilisateur de prendre une copie accidentelle ):

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

avec lequel votre sumtentative initiale devient:

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

En C ++ 17, avec CTAD, nous pouvons ajouter un guide de déduction:

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

Ce qui évite la nécessité de la fonction d'assistance. Nous pouvons simplement écrire y_combinator{[](auto self, ...){...}}directement.

En C ++ 20, avec CTAD pour les agrégats, le guide de déduction ne sera pas nécessaire.

J'ai une autre solution, mais je ne travaille qu'avec des lambdas sans état:

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

L'astuce ici est que les lambdas peuvent accéder aux variables statiques et vous pouvez convertir celles sans état en pointeur de fonction.

Vous pouvez l'utiliser avec des lambdas 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);
    };
}

Son travail dans GCC 4.7

Vous pouvez faire en sorte qu'une fonction lambda s'appelle elle-même de manière récursive. La seule chose que vous devez faire est de le référencer via un wrapper de fonction afin que le compilateur sache son type de retour et d'argument (vous ne pouvez pas capturer une variable - le lambda lui-même - qui n'a pas encore été définie) .

  function<int (int)> f;

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

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

Faites très attention à ne pas sortir de la portée du wrapper f.

Pour rendre lambda récursif sans utiliser de classes et de fonctions externes (comme std::functionou un combinateur à virgule fixe), on peut utiliser la construction suivante en C ++ 14 ( exemple en direct ):

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

imprime:

1
 2
  8
 3
  5
   7
  6
 4

Remarque: le type de résultat lambda doit être spécifié explicitement.

J'ai exécuté un benchmark comparant une fonction récursive à une fonction lambda récursive en utilisant la std::function<>méthode de capture. Avec des optimisations complètes activées sur la version 4.1 de clang, la version lambda fonctionnait beaucoup plus lentement.

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

Produit des résultats:

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

(Remarque: j'ai également confirmé avec une version qui prenait les entrées de cin, afin d'éliminer l'évaluation du temps de compilation)

Clang produit également un avertissement du compilateur:

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

Ce qui est attendu et sûr, mais doit être noté.

C'est formidable d'avoir une solution dans nos ceintures d'outils, mais je pense que le langage aura besoin d'une meilleure façon de gérer ce cas si les performances doivent être comparables aux méthodes actuelles.

Remarque:

Comme l'a souligné un commentateur, il semble que la dernière version de VC ++ a trouvé un moyen d'optimiser cela au point de performances égales. Peut-être n'avons-nous pas besoin d'une meilleure façon de gérer cela, après tout (sauf pour le sucre syntaxique).

De plus, comme certains autres articles SO l'ont souligné ces dernières semaines, les performances en elles- std::function<>mêmes peuvent être la cause du ralentissement par rapport à la fonction d'appel directement, du moins lorsque la capture lambda est trop grande pour s'adapter à certaines std::functionutilisations de l' espace optimisé par la bibliothèque pour les petits foncteurs. (Je suppose qu'un peu comme les diverses optimisations de chaînes courtes?).

Il s'agit d'une implémentation légèrement plus simple de l'opérateur de point de fixation qui rend un peu plus évident ce qui se passe.

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

Voici une version raffinée de la solution Y-combinator basée sur celle proposée par @Barry.

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

Pour l'utiliser, on pourrait faire ce qui suit

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

Il est similaire au let recmot - clé dans OCaml, mais pas le même.

C ++ 14: Voici un ensemble générique récursif anonyme sans état / sans capture de lambdas qui renvoie tous les nombres de 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<m)
        f(f, ++n, m);
},
    1, 20);

Si je comprends bien, cela utilise la solution du combinateur Y

Et voici la version somme (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

Voici la réponse finale pour le PO. Quoi qu'il en soit, Visual Studio 2010 ne prend pas en charge la capture de variables globales. Et vous n'avez pas besoin de les capturer car la variable globale est accessible globalement par define. La réponse suivante utilise plutôt une variable locale.

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

Vous essayez de capturer une variable (somme) que vous êtes en train de définir. Ça ne peut pas être bon.

Je ne pense pas que des lambdas C ++ 0x véritablement auto-récursifs soient possibles. Cependant, vous devriez pouvoir capturer d'autres lambdas.

Cette réponse est inférieure à celle des Yankes, mais quand même, la voici:

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

Vous avez besoin d'un combinateur à virgule fixe. Regarde ça .

ou regardez le code suivant:

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