Ubuntu-fr

Maneithel

[RÉSOLU] Parcourt d'arbre, C++ en prog fonctionnelle ? Foncteur

Bonjour !
Dans le cadre de mes cours, je n'ai jamais eu l'occasion de voir les fonctionnalités "programmation fonctionnelle" du C++ et je cherche des pistes pour un certain algo.  Voici le contexte.

class Noeud{
public:
    Noeud();         // constructeur
    void afficheLesEnfants();    // fonctions (par exemple... pour vous donner de 
    int compteLesEnfants();      // l'inspiration, à la place des traditionnels "foo" et "bar" ;-)
private:
    HashTable<clef, Noeud*> enfants;  // Un table de hachage contenant les enfants, d'autres nœuds
}

J'ai donc un arbre de Noeud, avec un nombre indéterminé de Noeud à chaque niveau.

Je voudrais une sorte de forEach qui appliquerais afficheLesEnfants() ou compteLesEnfants() à chaque enfant et sous enfant de mon arbre.  Une fonction qui ne sert qu'à parcourir l'arbre et appliquer une fonction membre à chaque élément (ou, éventuellement, à chaque élément répondant à un critère), peu importe la fonction cette fonction en fait...

Par contre, je n'ai aucune idée de comment travailler avec des pointeurs sur fonction, etc.

Quelqu'un a une piste ?

Merci beaucoup d'avance !

P.S. Je ne peux utiliser que Qt et la STL, puisque c'est dans le cadre d'un cours (je tiens à spécifier que ce n'est pas l'essence du cours du tout (c'est un cours d'OpenGL), c'est un petit ajout personnel, pour satisfaire ma curiosité et donner un plus value à mon apprentissage)

EDIT j'ai changé le nom de cette discution pour mieux représenter son contenu.  Le nom d'origine est  "Parcourt d'arbre, C++ en prog fonctionnelle ?"

Dernière modification par Maneithel (Le 18/03/2011, à 15:49)

Mindiell

Re : [RÉSOLU] Parcourt d'arbre, C++ en prog fonctionnelle ? Foncteur

On va prendre AfficherLesEnfants alors (je préfère les méthodes à l'infinitif, c'est plus parlant je trouve ):

class Noeud
{
public:
   Noeud();
   void AfficherLesEnfants();
   unsigned int CompterLesEnfants();
private:
   void Afficher();

   vector<Noeud> _enfants; // Je prends un vecteur plutôt qu'une table de hachage, je sais faire de tête ;)
}

void Noeud::AfficherLesEnfants()
{
   // On affiche d'abord le Noeud lui-même
   Afficher();
   // Puis ses enfants, s'il en possède
   for (unsigned int i=0;i<_enfants.size();i++)
   {
      _enfants[i].AfficherLesEnfants();
   }
}

Ainsi, en appelant AfficherLesEnfants, tu auras la liste de chaque enfant et pour chaque enfant, ses enfants, etc...
Cest ce que tu voulais ?

Dernière modification par Mindiell (Le 17/03/2011, à 10:34)

---

Développeur indépendant

ehmicky

Re : [RÉSOLU] Parcourt d'arbre, C++ en prog fonctionnelle ? Foncteur

Si tu veux exécuter le code que tu veux, plutôt que d'utiliser un pointeur de fonction, tu peux passer un functor en argument. C'est plus flexible, tu peux par exemple faire en sorte que deux invocations successives du functor avec des arguments identiques donnent des résultats différents.
En plus, ça te permettra d'utiliser plus facilement les algorithmes sur les containers de la STL, comme for_each, etc.

Dernière modification par ehmicky (Le 17/03/2011, à 17:29)

---

Stego++, bibliothèque libre de stéganographie (avec cryptographie), à venir !
Besoin de votre aide :
Stats sur les compilateurs C++ les plus utilisés
Comment utiliser les archetypes C++ ?

dde63a

Re : [RÉSOLU] Parcourt d'arbre, C++ en prog fonctionnelle ? Foncteur

J'ai eu dans son temps à traiter des cas, dit de nomenclature en base de données : un produit fini, ses composants et pour chacun de ces derniers leurs propres composants et ainsi de suite.
La fonction est dite récursive et nécessite un test de fin pour éviter une boucle infinie.

---

Le doute raisonnable est facteur de progrès

Maneithel

Re : [RÉSOLU] Parcourt d'arbre, C++ en prog fonctionnelle ? Foncteur

On va prendre AfficherLesEnfants alors (je préfère les méthodes à l'infinitif, c'est plus parlant je trouve ):

class Noeud
{
public:
   Noeud();
   void AfficherLesEnfants();
   unsigned int CompterLesEnfants();
private:
   void Afficher();

   vector<Noeud> _enfants; // Je prends un vecteur plutôt qu'une table de hachage, je sais faire de tête ;)
}

void Noeud::AfficherLesEnfants()
{
   // On affiche d'abord le Noeud lui-même
   Afficher();
   // Puis ses enfants, s'il en possède
   for (unsigned int i=0;i<_enfants.size();i++)
   {
      _enfants[i].AfficherLesEnfants();
   }
}

Ainsi, en appelant AfficherLesEnfants, tu auras la liste de chaque enfant et pour chaque enfant, ses enfants, etc...
Cest ce que tu voulais ?

En fait, pas vraiment.  Dans le problème réel, j'ai 15 ou 20 méthodes différente et le but est d'utiliser un seul algorithme de parcourt valable pour toutes les utilisations.

Si tu veux exécuter le code que tu veux, plutôt que d'utiliser un pointeur de fonction, tu peux passer un functor en argument. C'est plus flexible, tu peux par exemple faire en sorte que deux invocations successives du functor avec des arguments identiques donnent des résultats différents.
En plus, ça te permettra d'utiliser plus facilement les algorithmes sur les containers de la STL, comme for_each, etc.

Très intéressant, j'en connais rien mais je pense que c'est ce qu'il me faut.  Restera à trouver une ressource plus parlante que wikipedia étant donné que j'ai jamais vu ça avant aujourd'hui ;-) et que c'est assez optionnel dans mon projet.  Par contre, c'est vraiment intéressant !  Mais j'ai de la difficulté à saisir le fonctionnement...

J'ai eu dans son temps à traiter des cas, dit de nomenclature en base de données : un produit fini, ses composants et pour chacun de ces derniers leurs propres composants et ainsi de suite.
La fonction est dite récursive et nécessite un test de fin pour éviter une boucle infinie.

Tout à fait, comme toute fonction récursive.

Dans les fait, du point de vue de l'algorithme lui-même, je vais d'abord essayer de le faire itératif pour éviter des problèmes de dépassement de capacité.  Par contre, si je dois itérer pour remplir une pile maison, ce n'est pas mieux que de faire une récursion qui rempli la pile d'éxécution  Si c'est trop compliqué à designer, je vais essayer une fonction récursive terminale locale à "parcourirArbre()" (à l'infinitif ) que, théoriquement, gcc devrait transformer en itération à la compilation et prévenir les possibilité de dépassement de capacité.  Sinon, quelque chose de très inspiré de "afficherLesEnfants()" de Mindiell suffira, mais générique et polymorphe.

Si je résume, parcourir un arbre est simple.  Mais le faire appliquer une méthode membre quelconque en même temps me bloque un peu.

en clair, j'ai besoin de quelque chose qui ressemblerais au pseudo code suivant

appliquerFAuxNoeudsRepondantALaContrainteCAPartirDuNoeudN( F, C, N) 
{
    Pour Chaque enfant et sous enfant de N
    Debut
        Si l'enfant courant répond au critère C
        Début
            F(enfant courrant)
        Fin
    Fin
}
// F une fonction a appliquer aux noeuds, C une fonction retournant un booléen, N un noeud.

Ce n'est donc pas le "Pour Chaque enfant et sous enfant de N" qui me cause probleme.
Si je pouvais coder ça en OCaml, se serait déjà fini .  Mais j'ai très envie de comprendre ces fonctionnement en C++.

Dernière modification par Maneithel (Le 17/03/2011, à 18:01)

ehmicky

Re : [RÉSOLU] Parcourt d'arbre, C++ en prog fonctionnelle ? Foncteur

Si tu veux exécuter le code que tu veux, plutôt que d'utiliser un pointeur de fonction, tu peux passer un functor en argument. C'est plus flexible, tu peux par exemple faire en sorte que deux invocations successives du functor avec des arguments identiques donnent des résultats différents.
En plus, ça te permettra d'utiliser plus facilement les algorithmes sur les containers de la STL, comme for_each, etc.

Très intéressant, j'en connais rien mais je pense que c'est ce qu'il me faut.  Restera à trouver une ressource plus parlante que wikipedia étant donné que j'ai jamais vu ça avant aujourd'hui ;-) et que c'est assez optionnel dans mon projet.  Par contre, c'est vraiment intéressant !  Mais j'ai de la difficulté à saisir le fonctionnement...

Bah en fait un functor, c'est juste une classe avec un operator() (overloadable operator sur parenthèses), ce qui fait qu'une fois instantiée, tu peux l'utiliser comme un pointeur de fonction. Tu peux faire hérité ton functor de classes prévues pour ça dans la STL, std::unary_function, et std::binary_function.
Je te donnerai bien un exemple, mais là faut que je finisse mon marketing

Dernière modification par ehmicky (Le 17/03/2011, à 18:07)

---

Stego++, bibliothèque libre de stéganographie (avec cryptographie), à venir !
Besoin de votre aide :
Stats sur les compilateurs C++ les plus utilisés
Comment utiliser les archetypes C++ ?

Maneithel

Re : [RÉSOLU] Parcourt d'arbre, C++ en prog fonctionnelle ? Foncteur

ok, j'ai presque lu un peu et j'envoie un essai.
Supposons que j'inclus les bons fichiers et les bons namespaces , disons que c'est un hybride pseudo-code/C++.

Foncteur

class AfficherNomDuNoeudFoncteur
{
public:
    void operator() (const Noeud* n)
    {
    cout << n->nom();
    }
}

Prédicat

class PredicatNomNonVide
{
public:
bool operator()(const Noeud* n){return n->nom().isEmpty()}
}

Parcourt

template <class T, class U>
void appliquerTAuxNoeudsRepondantALaContrainteUAPartirDuNoeudN(const T foncteur, const U contrainte, const Noeud* n)
{
    if (!n) return;
    for(ListeEnfant::iterator i = n->enfants.begin(), i != n->enfants.end(), i++)
    {
        if contrainte(i)
        {
            foncteur(i);
        }
        appliquerTAuxNoeudsRepondantALaContrainteUAPartirDuNoeudN(foncteur, contrainte, i)
    }
}    

Main

int main()
{
    Noeud n(chargerArbreDeNoeud("fichier")); // pour avoir un arbre de noeuds
    AfficherNomDuNoeudFoncteur f();            // instanciation du foncteur
    PredicatNomNonVide p();                          // instanciation du prédicat
    appliquerTAuxNoeudsRepondantALaContrainteUAPartirDuNoeudN(f, p, n);

    return 0;
}

La syntaxe devrait-elle ressembler à ça ? La structure ?  En somme, suis-je sur la bonne piste ?

ehmicky

Re : [RÉSOLU] Parcourt d'arbre, C++ en prog fonctionnelle ? Foncteur

Ouh là, tu te compliques la vie, tu peux utiliser std::for_each() pour appliquer ton functor à tous les éléments de ton container, quel qu'il soit (ici "enfants")

---

Stego++, bibliothèque libre de stéganographie (avec cryptographie), à venir !
Besoin de votre aide :
Stats sur les compilateurs C++ les plus utilisés
Comment utiliser les archetypes C++ ?

Maneithel

Re : [RÉSOLU] Parcourt d'arbre, C++ en prog fonctionnelle ? Foncteur

mais les enfants des enfants, je ne pense pas que for_each les parcoure aussi

ehmicky

Re : [RÉSOLU] Parcourt d'arbre, C++ en prog fonctionnelle ? Foncteur

Ah non, je savais pas que tu voulais faire récursif. Mais tu peux inclure la récursion dans le functor : Si le Node a des enfants -> faire un for_each() sur ses enfants. Ou tu peux avoir une fonction qui renvoie l'ensemble des nodes de manière récursive (à partir d'un point donné), sous forme de ListeEnfant.

Dernière modification par ehmicky (Le 17/03/2011, à 19:21)

---

Stego++, bibliothèque libre de stéganographie (avec cryptographie), à venir !
Besoin de votre aide :
Stats sur les compilateurs C++ les plus utilisés
Comment utiliser les archetypes C++ ?

Maneithel

Re : [RÉSOLU] Parcourt d'arbre, C++ en prog fonctionnelle ? Foncteur

J'ai en effet plusieurs options pour l'algo de parcourt.  Est-ce que j'en comprends que pour le coté functor de mon implémentation c'est pas mal ?

Mindiell

Re : [RÉSOLU] Parcourt d'arbre, C++ en prog fonctionnelle ? Foncteur

Personnellement, ça m'a l'air bien parti. Je ne connais pas bien les functor, plutôt un bête pointeur sur fonction, mais je pense que tu as cerné l'idée générale

PS : ParcourS, et non parcourT (qui est la forme du verbe)

Dernière modification par Mindiell (Le 18/03/2011, à 11:08)

---

Développeur indépendant

Maneithel

Re : [RÉSOLU] Parcourt d'arbre, C++ en prog fonctionnelle ? Foncteur

Merci beaucoup a tous.  Je mettrai ici un liens vers mon code quand j'aurai fini (au plus tard fin avril )