Post by Mihamina Rakotomandimby (R12y)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