Votre opinion sur le cours de ce matin :	Votre opinion sur le TD de la semaine dernière :

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.

Éléments d'un arbre binaire

1. Définir le type de données '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.)
2. Définir l'arbre a1 ci-dessous :
3. Définir une fonction elements : 'a tree -> 'a list qui renvoie la liste des éléments rencontrés lors d'un parcours infixe. L'assertion suivante devra être vérifiée :

   let () =
     assert (elements a1 = [2; 3; 5; 6; 8; 12; 15])
           

4. Définir une fonction fold : ('a -> 'b -> 'a) -> 'a -> 'b tree -> 'a. Si la fonction f : 'a -> 'b -> 'a, appliquée à un état et à un élément, renvoie un nouvel état, alors l'appel fold f s t doit appliquer la fonction f successivement à tous les éléments de l'arbre t, dans l'ordre infixe, à partir de l'état initial s, et doit renvoyer l'état final obtenu à l'issue de l'itération.
5. Utiliser la fonction fold pour définir une fonction size : 'a tree -> int qui calcule le nombre de nœuds internes d'un arbre. L'assertion suivante doit réussir :

   let () =
     assert (size a1 = 7)
           

6. Utiliser la fonction fold pour redéfinir la fonction elements. Tester cette nouvelle implémentation :

   let () =
     assert (elements a1 = [2; 3; 5; 6; 8; 12; 15])
           

   Comparer la complexité de ces deux définitions de elements.

Déposez votre fichier :

Comparaison d'arbres binaires bien ordonnés

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.

1. En utilisant la fonction 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 infixe). Par exemple, en notant a2 et a3 les arbres

   a2 =

   a3 =

   on devra avoir

   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 :

Itérateurs

La fonction de comparaison ci-dessus n'est pas vraiment efficace. Elle construit toujours les deux listes de tous les éléments des deux arbres, alors que si (par exemple) les premiers éléments des deux arbres diffèrent, on pourrait espérer détecter cela en temps constant. Ainsi, si les deux arbres suivants ont un million d'éléments chacun,

                         

type 'a iterator = ('a * 'a tree) list
      

1. Définir une fonction iterator : 'a tree -> 'a iterator qui crée un itérateur à partir d'un arbre. Il reste tout l'arbre à parcourir et l'itérateur est donc constitué de l'intégralité de la branche gauche de l'arbre. On pourra introduire une fonction intermédiaire de type 'a tree -> 'a iterator -> 'a iterator qui renvoie un itérateur parcourant les éléments d'un arbre (premier argument) puis tous les éléments d'un itérateur donné (second argument).
2. Définir une fonction 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é.
3. Redéfinir la fonction 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])
           

4. En utilisant deux itérateurs (et sans utiliser la fonction 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 un million ci-dessus). La tester :

   let () =
     assert (equal a1 a1);
     assert (equal a2 a3);
     assert (not (equal a1 a2))
           

Déposez votre fichier :

Questions bonus

Fonctorisation

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.

1. Définir le type

   module type EqualityType =
     sig
       type t
       val equal : t -> t -> bool
     end
           

   des modules contenant la définition d'un type (t) et d'une fonction de comparaison sur ce type (equal).
2. Définir un foncteur

   module Tree(ET : EqualityType) =
     struct
       type element = ET.t
   
       (* à compléter... *)
     end
           

   qui sera de type

   module Tree :
     functor (ET : EqualityType) ->
       sig
         type element = ET.t
         type t = element tree
         type iterator = (element * t) list
         val iterator : t -> iterator
         val next : iterator -> (element * iterator) option
         val equal : t -> t -> bool
       end
           

   permettant 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.
3. À l'aide de ce foncteur, définir le module 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 :

Itérateurs par continuation

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 infixe, en utilisant le mécanisme de clôtures d'OCaml. L'idée est de déclarer le type des itérateurs par

type 'a iterator = unit -> ('a * 'a iterator) option
     

# 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 cyclic
     

type 'a iterator =
  | I of (unit -> ('a * 'a iterator) option)
     

1. Définir la fonction next : 'a iterator -> ('a * 'a iterator) option.
2. Définir la fonction iterator : 'a tree -> 'a iterator correspondant au parcours infixe.
3. Définir la fonction elements : 'a tree -> 'a list en utilisant l'itérateur (comme en 3.3) et vérifier

   let () =
     assert (elements a1 = [2; 3; 5; 6; 8; 12; 15])
          

4. Définir la fonction equal : 'a tree -> 'a tree -> bool (comme en 3.4) et la tester.
5. Tout en gardant le même type pour 'a iterator, définir des fonctions
   • iterator_prefix : 'a tree -> 'a iterator
   • iterator_postfix : 'a tree -> 'a iterator
   correspondant respectivement à des parcours préfixe et postfixe, puis deux fonctions elements_prefix et elements_postfix. (On pourra généraliser elements pour qu'elle prenne iterator en argument.) Tester avec

   let () =
     assert (elements_prefix  a1 = [5; 2; 3; 8; 6; 15; 12]);
     assert (elements_postfix a1 = [3; 2; 6; 12; 15; 8; 5])
     

Déposez votre fichier :

Une solution vous est proposée.