Fonctions lambda récursives dans c ++0x

Question

je suis novice en c++0x, donc veuillez m'excuser si ma question est stupide :).

je suis en train d'écrire la suite récursive une fonction lambda, il ne 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:~/Étude/09C++/c++0x/lambda> g++ -std=c++0x sum.cpp

sum.cpp: En fonction lambda: la somme.rpc:18:36: erreur: ‘((*)) ->:: somme' ne peut pas être utilisé comme une fonction

la version de gcc

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

mais si je change la déclaration de la somme() comme ci-dessous, il 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 s'il vous plaît jeter la lumière sur cette?

Answer 1

Réfléchir à la différence entre l' auto et la version complètement spécifié, le type de version. L' auto mot-clé détermine son type de ce qu'il est initialisé avec, mais ce que vous êtes en l'initialisant avec besoin de savoir quel est son type (dans ce cas, le lambda fermeture besoins de connaître le type c'est de la capture). Quelque chose d'un poulet et des œufs problème.

D'autre part, un complètement spécifié, la fonction de type de l'objet n'a pas besoin de "savoir" quelque chose à propos de ce qui leur est assigné, et ainsi de le lambda de fermeture peut également être pleinement informé sur les types de sa capture.

Considérer cette légère modification de votre code et il peut faire 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);
};

Bien évidemment, cela ne marcherait pas avec l'auto. Récursive lambda fonctions fonctionnent parfaitement bien (à moins qu'ils n'en MSVC, où j'ai de l'expérience avec eux), c'est juste qu'ils ne sont pas vraiment compatible avec l'inférence de type.

Answer 2

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

Le truc ici est que lambdas peut 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

Answer 3

Vous pouvez appeler une fonction lambda elle-même de manière récursive. La seule chose à faire est de la référencer via un wrapper de fonction afin que le compilateur sache qu'il est renvoyé et son type d'argument (vous ne pouvez pas capturer une variable - la lambda elle-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 épuiser la portée de l'emballage. F.

Answer 4

J'ai couru un indice de référence de la comparaison d'une fonction récursive vs récursive une fonction lambda à l'aide de la std::function<> méthode de capture. Avec plein optimisations activées sur clang la version 4.1, le lambda version couru beaucoup plus lents.

#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

(Note: j'ai aussi confirmé avec une version qui a pris les entrées de cin, de façon à éliminer les temps de compilation d'évaluation)

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 prévu, et en toute sécurité, mais doivent être notées.

C'est génial d'avoir une solution dans notre toolbelts, mais je pense que la langue aurez besoin d'une meilleure façon de gérer ce cas, si la performance est comparable aux méthodes actuelles.

Note:

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

Aussi, comme certains autres, AFIN de postes ont indiqué ces dernières semaines, la performance de std::function<> lui-même peut être la cause de ralentissement vs appeler directement la fonction, au moins lorsque le lambda de capture est trop grand pour tenir dans une bibliothèque-espace optimisé std::function utilise pour les petits-foncteurs (je pense un peu comme les différents courte chaîne optimisations?).

Answer 5

Il s’agit d’une implémentation un peu plus simple de l’opérateur fixpoint qui rend un peu plus évident ce qui se passe exactement.

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