Bonjour,

Je me permet de vous poser cette colle qui me trôte dans la tête depuis deux jours.
J'ai ramené un certain problème assez compliqué au problème, qui me semblait assez simple, de reconstruction d'un arbre selon certaines règles.
L'arbre en question est définit pas le type inductif suivant :
type 'a arbre :=
mkArbre of 'a * (list ('a arbre));;

Pour la reconstruction, nous disposons :
-d'une fonction
fNoeud : 'a arbre -> truc -> 'a arbre

Truc est un "contexte" que l'on va faire grossir progressivement après chaque reconstruction de noeud.
Grâce à cette fonction fNoeud, on peut, étend donné un noeud et le contexte actuel connaître le "nouveau" noeud qui le remplacera (plus exactement l'arbre qui représente ce noeud).

- On dispose également d'une fonction
fOld : 'a arbre -> truc
qui permet de connaître le contexte actuel.
En clair, mon contexte est encodé quelque part dans mon arbre (peut importe où).

La règle de reconstruction :
-----------------------

La reconstruction doit s'opérer en largeur d'abord impérativement.
Vous comprendrez ce que cela change : pour chaque reconstruction de noeud, je dois passer un contexte, et je veux impérativement que ce contexte soit celui obtenu par la reconstruction du noeud juste avant dans un parcours en largeur d'abord.

Ex :

_______n1
_____/____\
____|______\
____n2______n3
___/_\_____/_\
__n4_n5___n6__n7

-Il faut que n1 soit recréé,
puis
-n2 (avec comme contecte "fOld n1"),
puis
-n3 (avec comme contexte "fOld n2"),
puis
-n4 (avec comme contexte "fOld n3");
puis
-n5 (avec comme contexte "fOld n4")
...

Au final, je veux obtenir l'arbre résultant de la transformation de tous les noeuds, dans l'ordre spécifié au dessus.

Bon, peut être que le problème n'est pas clairement formulé, auquel cas n'hésitez pas à me le dire et je reformulerais.

Voila, ce problème me pose problème, bien que très simple à comprendre.
Je précise que je ne peux écrire que des algorithmes fonctionnels.
Oubliez donc tout traitement impératif : le for, le while, etc... sont bannis. Ou plus précisément n'existent pas.

J'ai bien entendu fais un paquet de tentatives de définition de cette fonction, qui ont toutes échouées pour l'instant.
Je peux poster plus de détails sur mes essais, mais je ne voudrais pas que ça inhibe votre réflexion frais sur le problème (et puis épurer mes essais pour les rendre compréhensibles n'est pas évident, le problème posté ici n'étant pas exactement mon problème initial, que j'ai reformulé pour le poster ici).
Peut être que le fait de poster ici m'aura éclairci les idées, où que l'un d'entre vous aura une idée élégante.

Merci à tous ceux qui me consacreront un petit instant.

PS : Désolé pour les fautes d'orthographes, il est tard et mes yeux piquent :p

Je ne suis pas sûr d'avoir compris le problème, et je ne suis pas un spécialiste des langages fonctionnels donc je ne sais pas trop jusqu'à quel point ça te limite, mais d'après ce que j'ai compris je ferais un truc qui ressemblerait un peu à ça :

f(t : Noeud) {
traitement(t)
file.add(t.leftChild)
file.add(t.rightChild)
f(file, t)
}

f(file : Fifo, t : Noeud) {
traitement(file.getFirst(), t)
file.add(file.getFirst().leftChild)
file.add(file.getFirst().rightChild)
file.popFirst()
f(file, t)
}

Et normalement ça devrait s'exécuter à peu près comme ça :
f(n1)
----traitement(n1)
----file = [n2, n3]
----f(file, n1)
--------traitement(n2, n1)
--------file = [n3, n4, n5]
--------f(file, n2)
------------traitement(n3, n2)
------------file = [n4, n5, n6, n7]
------------etc.

Voilà c'est du pseudo-code pas rigoureux du tout, il manque pas mal de trucs mais j'espère que ça te donnera des idées (si j'ai bien compris ton problème, et j'en suis pas sûr du tout ).

Je ne sais pas si c'est parce qu'il était tard lors de l'écriture de l'énoncé ou parce qu'il est tôt pour mon pauvre neurone, mais j'ai un peu de mal à comprendre ce que tu veux faire et ce que tu as à ta disposition.
En particulier, la définition des fonctions fNoeud, fOld et de la fonction que tu veux créer et de leurs effets est assez cryptique.

A première vue, je ne distingue pas vraiment la sophistication par rapport à un simple parcours en largeur.

Merci pour vos réponses.

Aldebran, tu as parfaitement raison, j'ai bien sur pensé à un simple algorithme de parcours en largeur d'abord.
La seule différence pour moi est qu'en plus d'appliquer un traitement à tous les noeuds dans cet ordre là, c'est que je veux "reconstruire" l'arbre résultant de l'application de ces fameux traitements sur les noeuds.
Et c'est précisemment là que ça se complique un peu j'ai l'impression.

Mais je pense qu'avec quelques adaptations, ça doit pouvoir s'écrire de manière assez proche à ce que tu as écris.
Je vais y reflechir.

Concernant le fait que je n'ai la possibilité d'utiliser que de la programmation fonctionnelle pure, cela ne change pas grand chose en effet. Si ce n'est que du coup le seul moyen d'itérer un traitement sera la récursivité (et que je dois avoir des fonctions récursives bien formées : la "taille" de leur argument sur lequel s'établit la récursivité doit décroître pour assurer la terminaison).
Mais bon, ça ne change pas grand chose, et un algo impératif correct aura toujours son équivalent fonctionnel.

Kaoron, je pense que c'est moi qui n'ai pas du expliquer convenablement.
En clair, j'ai un arbre.
Je veux le reconstruire.
Pour chaque noeud, j'ai une fonction (fNoeud : 'a arbre -> truc -> 'a arbre) qui me donne l'image d'un noeud à partir du dit noeud et du contexte actuel.
Cependant attention, cette fonction prend un arbre et retour un arbre.
En réalité, ce qui m'intéressera sera uniquement de garder la partie "label" (le 'a), car les fils (la partie list ('a arbre)) devra être elle aussi reconstruite à la génération d'en dessous.

Par exemple, sur mon exemple, on veut obtenir à la fin l'arbre résultant :

_____________________label( fNoeud n1)

_____/____________________________________________
\

____|_____________________________________________
__|
label(fNoeud n2)_______________________________label(fNoeud n3)

___/_____________\________________________________
_/_________\
label(fNoeud n4)_label(fNoeud n5)__label(fNoeud n6)____label(...)

J'espère que ca ne sera pas trop horrible une fois posté.
A chaque fois que j'utilise ma fonction fNoeud sur un noeud (un arbre), j'obtiens un nouveau noeud (un arbre); pour lequel seul la partie "label" sera conservé effectivement. Pour les fils, il y aura traitement de la même manière.
En fait, ma fonction FNoeud aurait pu être de de type :
('a -> truc -> 'a) pour n'opérer que sur les labels directement, et ca aurait été surrement plus clair.
Mais bon, peut importe, on peut supposer l'un ou l'autre.

Je ne sais pas si c'est plus clair.
Je continue à relfechir au problème de mon coté.

Merci à vous !

Hum… j'avais zappé ce thread et j'ai répondu sur l'autre.

D'après ton exemple, ça semble effectivement être un map que tu veux.
La map c'est :

On prend
un objet de type 'a toto (un toto rempli d'objets de type 'a)
une fonction f de type 'a -> 'b
et ça renvoie un autre objet, de type 'b toto, construit en appliquant f à chaque élément de type 'a dans l'objet de type 'a toto initial.

Après, c'est à toi de voir dans le cas de tes arbres dans quel ordre tu veux traiter tes éléments de type 'a.

Non, ce n'est pas un map, car un map est "parallèle".
Comprendre par là, que même si implémenté de manière séquentielle (sans parallélisme), il serait possible de le paralléliser.
Formellement, pour A = map f B, (B = [B1...Bn])
nous avons les Ai qui sont calculés indépendamment les uns des autres.

Et justement, je ne veux pas cette indépendance.
Car, pour un niveau p de profondeur fixé, si j'appelle Np la liste des noeuds de cette profondeur, le calul de l'image de chaque (Np)i dépend de l'image de (Np)i-1.
Et (Np)0 dépend de (Np-1)n.
Et cela à à cause de ce "contexte" que je dois faire grossir, noeud après noeud, dans cette organisation "en largeur d'abord".

Il te faut deux listes pour construire un arbre en largeur :
- une liste de labels.
- une liste de degrés.

Si j'ai correctement intuité ce qui te pose problème, ça devrait te permettre de le résoudre.

Merci pour votre intéret à mon problème.

Qu'appelles-tu liste de degrés Kaoron ?
J'imagine que c'est une liste de repères de positionnement des labels, pour garder l'information de "où ils doivent être", mais je n'en suis pas sur.

Je vais essayer de creuser ton idée, merci !

« Non, ce n'est pas un map, car un map est "parallèle". » non. Un map fait les calculs dans l'ordre imposé par ton implantation du map (en l'occurence, un parcours en largeur ici).

« Qu'appelles-tu liste de degrés Kaoron ? »
Une liste du nombre d'arcs sortant d'un noeud.

En parcourant tes noeuds en largeur, tu peux créer deux listes :
Une liste de labels, ordonnés par ton parcours sur lesquels tu peux dans l'ordre appliquer ta fonction fNoeud(a'[n], fOld(a'[n-1))
Une liste du nombre d'enfants du noeud considéré.

Soit l'arbre :
1->2,3
2->4,5
3->6,7
4->vide
5->8
6->vide
7->vide
8->vide

Un parcours en largeur d'abord de cet arbre (contraint par l'ordre des listes d'adjacences) visite les noeuds dans l'ordre:
1,2,3,4,5,6,7,8
et tu peux lister le nombre d'enfants de chaque noeud:
2,2,2,0,1,0,0,0

Ce que tu utiliseras pour reconstruire ton arbre :
le premier noeud est la racine, il a deux enfants, ces deux enfants sont les noeuds suivants dans le parcours.
1->2,3
le second noeud a deux enfants, qui sont les suivants non visités
2->4,5

Et ainsi de suite.

Huum, merci beaucoup Kaoron, ça me semble être une très bonne idée !
Je n'aurais pas pensé que juste le degré de mes noeuds accompagné par les noeuds dans leur ordre "largeur d'abord" me permettait de reconstruire l'arbre.
J'aurais eu tendance à penser qu'il fallait plus d'information que ça.
Enfin bref, tu as je pense trouvé une solution à mon problème.
Reste à voir si ça s'implémente facilement et si je pourrais assez facilement démontrer des propriétés sur cet algo.

Chris_27 :
Il fallait lire la phrase suivante :
<< Comprendre par là, que même si implémenté de manière séquentielle (sans parallélisme), il serait possible de le paralléliser. >>

Alors que dans mon problème, il est rigoureusement impossible de calculer des Ai en parallèle.
Mais je suis d'accord avec ton, un map execute ordinairement de manière séquentielle suivant la manière dont il a été implémenté.
Mais je voulais parler de "possibilité de parralélisme", qui créait cette indépendance entre les Ai.

Merci à tous ceux qui m'ont consacré de leur (precieux) temps.
Je vous donnerait des nouvelles sur la faisabilité de l'approche de Kaoron pour mes besoins.

Moi je n'imagine pas un map sans un parcours de ta structurée de données : comme tu récupères les éléments de type 'a dans ta structure sans la parcourir ?

Sinon, je vais te donner un compte rendu de ce que j'ai dit sur IRC : en gros, je me demande (c'est une question) si tu as pris assez de recul sur ton problème et bien choisi la structure de données pour le résoudre. Mon but n'est pas de te remettre en cause, mais plutôt de te suggérer qu'un peu de reflexion en amon pourrait permettre de simplifier les choses.

Typiquement, si ton 'a est mutable, ton problème se réduit exactement à un parcours en largeur de l'arbre + traitement des noeuds au fur et à mesure pour modifier leur état, ce qui est plus simple que de devoir reconstruire un autre arbre (plus besoin de la "liste des degrés").