arbre_vers_liste
est donc une variation d'un grand
classique : l'affichage d'un arbre sous forme préfixe.
let rec arbre_vers_liste a = match a with | Feuille Blanc -> [Zero ; Zero] | Feuille Noir -> [Zero ; Un ] | Noeud (a1,a2,a3,a4) -> Un::arbre_vers_liste a1 @ arbre_vers_liste a2 @ arbre_vers_liste a3 @ arbre_vers_liste a4 |
Toutefois, cette solution est truffée de concaténations de listes
(dénotées par « @
»).
C'est dommage, car il y a alors des recopies de listes en pagaille.
Une meilleure solution consiste à ajouter un argument dit de continuation
(noté k) et qui contient la suite de la liste à construire.
Autrement dit, la mission de do_arbre_vers_liste
a k est de renvoyer
la représentation sous forme de liste de a, suivie de la liste k.
let rec do_arbre_vers_liste a k = match a with | Feuille Blanc -> Zero :: Zero :: k | Feuille Noir -> Zero :: Un :: k | Noeud (a1,a2,a3,a4) -> Un:: do_arbre_vers_liste a1 (do_arbre_vers_liste a2 (do_arbre_vers_liste a3 (do_arbre_vers_liste a4 k))) let arbre_vers_liste a = do_arbre_vers_liste a [] |
La liste résultat est ainsi construite à partir de la fin, sans que le code soit bien compliqué. Outre une plus grande rapidité, ce second code a l'avantage de consommer moins d'espace de pile.