arbre quelconque
Harimalala Andotiana
Je suis débutante en ocaml et je suis entraine de travailler sur les
arbres quelconques (arbre dont le nombre de fils est varié),
Je voudrais savoir comment ajouter des fils sur un arbre quelconque en
ocaml.
Merci d'avance.
Mihamina Rakotomandimby (R12y)
> Je voudrais savoir comment ajouter des fils sur un arbre quelconque en
> ocaml.
(Contexte: On travaille ensemble sur le sujet, elle et moi)
J'ai essayé de decomposer le problème:
J'essaie d'abord de faire une fonction recursive qui prend un arbre en
argument (et eventuellement un arbre tampon en second) et qui retourne
ce meme arbre.
Je n'y arrive pas:
type 'a arbre = Av | N of 'a * 'a arbre list ;;
let rec retourner_arbre arbre tampon =
match a with
N(e,l) -> (* un truc avec "tampon" *)
;;
C'est pas évident pour moi.
Des pistes?
jchampavere
> Je voudrais savoir comment ajouter des fils sur un arbre quelconque en
> ocaml.
- On ajoute des fils � un nœud, pas � un arbre.
- � quel endroit les fils doivent-ils �tre ajout�s ?
Harimalala Andotiana
Mihamina Rakotomandimby (R12y)
> type 'a arbre = Av | N of 'a * 'a arbre list ;;
> let rec retourner_arbre arbre tampon =
Ce que je souhaite faire avec cette function c'est retourner l'arbre
"arbre" en le parcourant, c'est à dire que c'est au fur et à mesure du
parcours de "arbre" que je fabrique "tampon".
Je me rend compte que ce n'est pas aussi simple que cela...
bluestorm
Pourquoi utiliser un accumulateur/tampon ?
On peut coder directement sans paramètre supplémentaire :
- si c'est Av on renvoie Av (pourquoi Av ? Je trouve "Nil" ou "Leaf"
plus clair)
- si c'est un noeud, on retourne un noeud qui contient la même valeur
de type 'a, et pour chaque fils le retour de retourner_arbre. On a
donc besoin de l'opération qui prend une fonction et une liste
d'objets, et qui renvoie la liste des images de ces objets par la
fonction ( [a; b; c] -> [f(a); f(b); f(c)]). C'est la fonction
List.map :
type 'a tree = Nil | Tree of 'a * 'a tree list
let rec retourner_arbre = function
| Nil -> Nil
| Tree (elem, fils) -> Tree (elem, List.map retourner_arbre) fils
Si tu voulais quelque chose de tail-recursif (ce que je suggère ton
paramètre "tampon"), c'est possible (avec par exemple des
continuations) mais plus compliqué, tu ne devrais pas t'en occuper et
viser simple.
Jogo
> Les fils doivent être ajoutés sur l'un des noeuds (sur un noeud quelconque)
let add_stupid tree node =
match (tree,node) with
| (Av,y) -> y
| (x,Av) -> x
| (N (v,l), n) -> N (v, n::l)
Mais je ne dois pas avoir compris la question. Vous pourriez par
exemple nous donner la signature de la fonction.
--
Mes AAD réveillent les morts et redonnent les érections, l'amour,
le retour de l'épouse, le travail et l'argent.
-- Grand Mage Bonaventure Isaac Pochard dans fufe --
Joe Cool
> J'ai essayé de decomposer le problème:
> J'essaie d'abord de faire une fonction recursive qui prend un arbre en
> argument (et eventuellement un arbre tampon en second) et qui retourne
> ce meme arbre.
On part du type des arbres (du moins celui qui a été proposé):
type 'a tree = Nil | Node of 'a * 'a tree list
Pour retourner un arbre, il faut savoir retourner la liste des fils d'un
nœud. La fonction List.rev le fait déjà, mais nous allons tout de même
la reprogrammer. Le principe est de transférer le contenu d'une
liste-source dans une liste-destination comme on dépilerait une pile
d'assiette pour la re-empiler ailleurs; cette liste-destination sera
dénotée par acc:
let rec rev_aux acc = function
| [] -> acc
| h :: t -> rev_aux (h :: acc) t
On écrit alors aisément la fonction qui retourne une liste en partant
d'une liste-destination vide:
let rev_list l = rev_aux [] l
Mais la fonction rev_tree qui retourne un arbre devra être appliquée
récursivement sur chacun des fils du nœud en cours. On va alors enrichir
la fonction rev_list pour qu'elle applique une fonction f (qui sera
rev_tree) à chaque élément empilé:
let rec revapply_aux f acc = function
| [] -> acc
| h :: t -> rev_aux ((f h) :: acc) t
let revapply l = revapply_aux [] l
Maintenant on peut écrire directement la fonction de retournement d'un
arbre:
let rec rev_tree = function
| Nil -> Nil
| Node (n, cl) -> Node (n, revapply rev_tree cl)
Quand on programme, il ne faut pas hésiter à programmer une grande
quantité de fonctions annexes (elles rendent le code plus lisible et
plus modulaire), quitte à condenser le code une fois qu'il fonctionne:
let rec rev_tree = function
| Nil -> Nil
| Node (n, cl) ->
let rec revapply acc = function
| [] -> acc
| h :: t -> revapply ((rev_tree h) :: acc) t
in
Node (n, revapply [] cl)
Les plus paresseux essaieront d'utiliser les fonctions prédéfinies; on
obtient un code plus court, sans doute au prix d'une perte en efficacité:
let rec rev_tree = function
| Nil -> Nil
| Node (n, cl) -> Node (n, List.map rev_tree (List.rev cl))
--
Joe Cool
bluestorm
> Les plus paresseux essaieront d'utiliser les fonctions prédéfinies; on
> obtient un code plus court, sans doute au prix d'une perte en efficacité:
>
> let rec rev_tree = function
> | Nil -> Nil
> | Node (n, cl) -> Node (n, List.map rev_tree (List.rev cl))
Les vrais paresseux savent que List.rev_map existe.
let rec rev_tree = function
| Nil -> Nil
| Node (n, cl) -> Node (n, List.rev_map rev_tree cl)
Joe Cool
> On 16 jan, 19:58, Joe Cool <zierou...@free.fr> wrote:
>> Les plus paresseux essaieront d'utiliser les fonctions prédéfinies; on
>> obtient un code plus court, sans doute au prix d'une perte en efficacité:
>>
>> let rec rev_tree = function
>> | Nil -> Nil
>> | Node (n, cl) -> Node (n, List.map rev_tree (List.rev cl))
>
> Les vrais paresseux savent que List.rev_map existe.
C'est rassurant. Encore quelques jours et on nous montrera que rev_tree
existe également.
--
Joe Cool
Mihamina Rakotomandimby (R12y)
>>> let rec rev_tree = function
>>> | Nil -> Nil
>>> | Node (n, cl) -> Node (n, List.map rev_tree (List.rev cl))
>> Les vrais paresseux savent que List.rev_map existe.
> C'est rassurant. Encore quelques jours et on nous montrera que rev_tree
> existe également.
Et au passage, merci à tous, hein.