L'objectif de ce TD est d'implémenter de façon efficace le parcours d'arbres binaires à l'aide d'itérateurs. L'implémentation sera réalisée en OCaml.
'a tree
des arbres binaires dont
les nœuds internes portent un élément de type 'a
et dont
les feuilles ne portent aucune information. (On
notera Node
le constructeur des nœuds internes et Empty
le constructeur des feuilles.)
a1
ci-dessous :
elements : 'a tree -> 'a list
renvoyant la liste des éléments rencontrés lors d'un parcours
préfixe. L'assertion suivante devra être vérifiée :
let () = assert (elements a1 = [2; 3; 5; 6; 8; 12; 15])
elements
est-elle linéaire
? Si ça n'est pas le cas proposer une nouvelle implémentation qui soit
linéaire.elements_append : 'a tree -> 'a list -> 'a list
qui sera telle que l'on ait elements_append t xs = (elements t) @
xs
, et on définira
let elements t = elements_append t []
fold : ('a -> 'b -> 'a) -> 'a -> 'b tree ->
'a
qui applique successivement une fonction à un état et à une
étiquette pour renvoyer un nouvel état, les étiquettes étant parcourues
de façon préfixe.
fold
pour définir une
fonction size : 'a tree -> int
qui calcule le nombre de
nœuds d'un arbre et la tester :
let () = assert (size a1 = 7)
fold
pour redéfinir la
fonction elements
. Tester cette nouvelle implémentation :
let () = assert (elements a1 = [2; 3; 5; 6; 8; 12; 15])
Déposez votre fichier :
Dans la suite, on supposera que nos arbres sont bien ordonnés,
c'est-à-dire que le résultat de elements
est toujours une
liste triée de façon croissante, comme dans l'exemple a1
ci-dessus. En utilisant une variante de ces arbres, on peut par exemple
stocker efficacement les éléments d'un (multi-)ensemble.
elements
, définir une
fonction equal : 'a tree -> 'a tree -> bool
qui détermine
si deux arbres (bien ordonnés) contiennent les mêmes éléments (lorsqu'on
les parcourt dans l'ordre préfixe). Par exemple, en
notant a2
et a3
les arbres
a2 =
|
a3 =
|
let () = assert (equal a1 a1); assert (equal a2 a3); assert (not (equal a1 a2))Notez que, bien qu'ayant des formes différentes, ces deux arbres sont considérés comme égaux car ils représentent les mêmes ensembles d'éléments.
Déposez votre fichier :
Remarquons que le fonction de comparaison n'est pas vraiment efficace. Par exemple, on est toujours obligé de construire la liste de tous les éléments des deux arbres, alors que l'on pourrait directement s'apercevoir que deux arbres diffèrent si leurs premiers éléments diffèrent. Par exemple, si les deux arbres suivants ont 1 million d'éléments,
type 'a iterator = 'a tree list
iterator : 'a tree -> 'a iterator
qui
crée un itérateur à partir d'un arbre : avant de débuter le parcours
d'un arbre, il reste tout l'arbre à parcourir.
next : 'a iterator -> ('a * 'a iterator)
option
qui renvoie le prochain élément d'un itérateur ainsi
que l'itérateur correspondant à la suite du parcours. La fonction devra
renvoyer None
lorsque le parcours est terminé.
elements : 'a tree -> 'a list
en
utilisant un itérateur et la tester :
let () = assert (elements Empty = []); assert (elements a1 = [2; 3; 5; 6; 8; 12; 15]); assert (elements a2 = [2; 3]); assert (elements a3 = [2; 3])
elements
ci-dessus) redéfinir la
fonction equal : 'a tree -> 'a tree -> bool
. La fonction
devra renvoyer false
dès que deux éléments distincts sont
trouvés (elle s'arrêtera donc à la première étape sur l'exemple des deux
arbres de taille 1 million ci-dessus). La tester :
let () = assert (equal a1 a1); assert (equal a2 a3); assert (not (equal a1 a2))
Déposez votre fichier :
Nous avons mentionné que les arbres bien ordonnés (de type 'a
tree
) sont souvent utilisés pour représenter des ensembles de
valeurs de type 'a
, pour un type 'a
quelconque. En particulier, rien ne nous empêche de manipuler des
ensembles d'ensembles de valeurs, représentés par des valeurs de
type 'a tree tree
. Cependant, pour comparer les éléments d'un
arbre, nous avons jusqu'à présent utilisé l'opération de comparaison
standard de OCaml (=
), alors que l'on souhaiterait utiliser
la comparaison définie ci-dessus pour comparer les étiquettes d'un arbre
de type 'a tree tree
.
Afin de régler ce problème, nous allons encapsuler les fonctions définies à la partie 3 dans un foncteur dont le paramètre va permettre de spécifier l'ordre que nous souhaitons considérer sur les éléments d'un arbre.
module type EqualityType = sig type t val equal : t -> t -> bool enddes modules contenant la définition d'un type (
t
) et d'une
fonction de comparaison sur ce type (equal
).
module Tree(ET : EqualityType) = struct type element = ET.t (* à compléter... *) endqui sera de type
module Tree : functor (ET : EqualityType) -> sig type element = ET.t type t type iterator = t list val iterator : t -> iterator val next : iterator -> (element * iterator) option val equal : t -> t -> bool endpermettant de créer un module offrant des fonctions sur les arbres en utilisant la fonction du module
ET
en paramètre pour
comparer ses éléments.
TT
des arbres
d'arbres d'entiers et le tester :
let () = let a23 = Node (Empty, a2, Node (Empty, a3, Empty)) in let a32 = Node (Empty, a3, Node (Empty, a2, Empty)) in let a32' = Node (Node (Empty, a3, Empty), a2, Empty) in assert (TT.equal a23 a32); assert (TT.equal a23 a32')
Déposez votre fichier :
Précédemment, nous avons implémenté les itérateurs pour le parcours préfixe. Nous allons maintenant définir les itérateurs pour un autre type de parcours : le parcours infixe. Celui-ci est beaucoup plus utilisé que le précédent en pratique (mais un peu moins simple à implémenter).
a1
'a iterator_infix
qui permette de coder «
ce qu'il reste à faire dans un parcours infixe ».
iterator : 'a tree -> 'a iterator_infix
permettant de créer un itérateur à partir d'un arbre.
next : 'a iterator_infix -> ('a * 'a
iterator_infix) option
.
elements : 'a tree -> 'a list
et la
vérifier avec l'arbre a1
:
let () = assert (elements a1 = [3; 5; 2; 8; 6; 15; 12])
Déposez votre fichier :
La définition d'un itérateur, telle que nous l'avons considérée jusqu'à présent, nécessite de définir une structure de donnée spécialisée, qu'il n'est pas toujours aisé d'inventer, et qui est différente pour chaque façon de parcourir l'arbre. Nous allons maintenant considérer une autre façon d'implémenter l'itérateur pour le parcours préfixe, en utilisant le mécanisme de clôtures de OCaml. L'idée est de déclarer le type des itérateurs par
type 'a iterator = unit -> ('a * 'a iterator) optionet de considérer qu'un itérateur
i
est une fonction telle
que i ()
renvoie la valeur du prochain élément dans le
parcours ainsi que le nouvel itérateur (ou None
si le parcours
est terminé). Pour des raisons techniques liées au typage, il n'est pas
possible de déclarer ce type directement de cette façon car le
type 'a iterator
apparaît à droite de la définition :
# type 'a iterator = unit -> ('a * 'a iterator) option;; Characters 4-52: type 'a iterator = unit -> ('a * 'a iterator) option;; ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Error: The type abbreviation iterator is cyclicIl est cependant aisé de contourner ce problème en utilisant un type algébrique avec un unique constructeur (on peut définir récursivement un type si l'appel récursif est dans un constructeur). On définira donc
type 'a iterator = | I of (unit -> ('a * 'a iterator) option)
next : 'a iterator -> ('a * 'a iterator)
option
.
iterator : 'a tree -> 'a iterator
correspondant au parcours préfixe.
elements : 'a tree -> 'a list
en
utilisant l'itérateur et vérifier
let () = assert (elements a1 = [2; 3; 5; 6; 8; 12; 15])
equal : 'a tree -> 'a tree ->
bool
et la tester.
'a iterator
, définir une fonction
iterator_infix : 'a tree -> 'a iteratoret la tester à l'aide de la fonction
elements
correspondante. On pourra généraliser cette dernière fonction afin
qu'elle prenne le créateur d'itérateur en argument :
elements : ('a tree -> 'a iterator) -> 'a tree -> 'a list
.
Déposez votre fichier :
Le parcours postfixe d'un arbre consiste pour chaque nœud à explorer le fils gauche, puis le fils droit, puis l'élément du nœud.
iterator_postfix : 'a tree -> 'a iteratorqui crée un itérateur par continuation pour le parcours postfixe.
type 'a iterator_postfix(on pourra utiliser un type spécialisé ou des continuations) ainsi que les fonctions associées
iterator : 'a tree -> 'a iterator_postfix next : 'a iterator_postfix -> ('a * 'a iterator_postfix) option elements : 'a tree -> 'a listOn vérifiera
let () = assert (elements a1 = [5; 3; 8; 15; 12; 6; 2])
Déposez votre fichier :
Le parcours en largeur consiste à explorer d'abord la racine, puis les nœuds à distance 1 de la racine, puis ceux à distance 2, etc.
'a queue
de files (premier entré, premier
sorti) immuables (on n'utilisera pas de référence ou plus
généralement de structures de données mutables), ainsi que les fonctions
suivantes
empty : 'a queue
: la file videpush : 'a queue -> 'a -> 'a queue
: ajout d'un élément à la fin d'une filepop : 'a queue -> ('a * 'a queue) option
:
retrait du premier élément d'une file'a queue = 'a list
sera
acceptable).
iterator_width : 'a tree -> 'a iterator
qui crée un
itérateur pour le parcours en largeur. La tester sur la
fonction elements
correspondante :
let () = assert (elements a1 = [2; 3; 6; 5; 8; 12; 15])
Déposez votre fichier :
Pour un traitement plus général des itérateurs sur des structures arborescentes, on pourra se référer à l'article The Zipper de Gérard Huet.