recursive Fonctions lambda récursives en C++ 11




fonction récursive python (11)

L'astuce consiste à introduire dans l'implémentation lambda elle-même 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;
    else 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 d'abord trouvé ce truc facile à http://pedromelendez.com/recursive-lambdas-in-c14/

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

Je suis nouveau à C ++ 11. J'écris la fonction lambda récursive suivante, mais elle 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: Dans la fonction lambda: sum.cpp: 18: 36: erreur: ' ((<lambda(int, int)>*)this)-><lambda(int, int)>::sum ' ne peut pas être utilisé en tant que 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 éclairer cela?


Voici la réponse finale pour l'OP. 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 la variable locale à la place.

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

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

#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 prenait les entrées de cin, afin d'éliminer l'évaluation de la compilation)

Clang produit également un avertissement de 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 devrait être noté.

C'est génial d'avoir une solution dans nos ceintures à outils, mais je pense que le langage aura besoin d'un meilleur moyen de gérer ce cas si les performances doivent être comparables aux méthodes actuelles.

Remarque:

Comme un intervenant l'a fait remarquer, il semble que la dernière version de VC ++ ait trouvé un moyen d'optimiser cela jusqu'à atteindre des performances égales. 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).

En outre, comme d'autres postes SO l'ont souligné ces dernières semaines, les performances de std::function<> peuvent être à l'origine du ralentissement par rapport à la fonction d'appel, au moins lorsque la capture lambda est trop importante pour être intégrée dans une bibliothèque optimisée. L'espace std::function utilise pour les petits-foncteurs (je suppose un peu comme les différentes optimisations de chaînes courtes?).


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

Je ne pense pas que les LAMBDAS C ++ 0x auto-récursives soient possibles. Vous devriez être capable de capturer d'autres lambdas, cependant.


Vous avez besoin d'un combinateur de points fixes. Voir this .

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

Vous pouvez faire qu'une fonction lambda s'appelle récursivement. La seule chose que vous devez faire est de le référencer à travers un wrapper de fonction pour que le compilateur connaisse son type return et 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 de ne pas manquer la portée de l'encapsuleur f.


C'est 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 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';
    }
}

J'ai une autre solution, mais je travaille uniquement avec les lambdas sans état:

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

Trick ici est que lambdas peut accéder aux variables statiques et vous pouvez convertir les stateless 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


Avec C ++ 14, il est maintenant assez facile de faire un lambda récursif efficace sans avoir à supporter le surcoût supplémentaire de std::function , en quelques lignes de code (avec une petite modification par rapport à 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 tentative de sum origine 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);
  }
});

Pour rendre lambda récursif sans utiliser de classes et de fonctions externes (comme std::function ou combinator à virgule fixe), on peut utiliser la construction suivante dans C ++ 14 ( exemple live ):

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

impressions:

1
 2
  8
 3
  5
   7
  6
 4

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


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 qu'il a initialisé, mais ce que vous l'initialisez nécessite de connaître son type (dans ce cas, la fermeture de lambda doit connaître les types qu'il capture). Quelque chose d'un problème de poule et d'oeuf.

D'autre part, un type d'objet de fonction entièrement spécifié n'a pas besoin de "savoir" quoi que ce soit sur ce qui lui est assigné, et donc la fermeture de lambda peut également être entièrement informée sur les types qu'elle 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);
};

Évidemment, cela ne fonctionnerait pas avec auto . Les fonctions lambda récursives fonctionnent parfaitement bien (du moins en 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.





lambda