Itérateurs

par Samuel Mimram

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

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.)
Définir l'arbre a1 ci-dessous :
Définir une fonction 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])
        
```
Quelle est la complexité de l'opération de concaténation de deux listes ? La complexité de votre fonction elements est-elle linéaire ? Si ça n'est pas le cas proposer une nouvelle implémentation qui soit linéaire.
Indication : on pourra utiliser une fonction auxiliaire 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 []
        
```
Définir une fonction 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.
Utiliser la fonction 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)
        
```
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])
        
```

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.

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 préfixe). 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

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,

on n'a clairement pas besoin de construire deux listes d'un million d'éléments pour s'apercevoir que les premiers éléments diffèrent. Dans la suite, nous allons utiliser des itérateurs afin de parcourir les éléments des arbres sans avoir à construire toute la liste. Un itérateur est ici une liste d'arbres restant à parcourir pour terminer le parcours préfixe. On définira leur type par

type 'a iterator = 'a tree list

Définir une fonction 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.
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é.

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])

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 1 million ci-dessus). La tester :
```
let () =
  assert (equal a1 a1);
  assert (equal a2 a3);
  assert (not (equal a1 a2))
        
```

Déposez votre fichier :

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.

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).

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
      type iterator = 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.

À 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 :

Parcours infixe

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).

Le parcours infixe d'un arbre consiste, pour chaque nœud, à explorer le fils gauche, puis l'élément du nœud, puis le fils droit. Quelle est la liste des éléments rencontrés lors d'un parcours infixe pour l'abre a1 donné en premier exemple ?
Définir un type 'a iterator_infix qui permette de coder « ce qu'il reste à faire dans un parcours infixe ».
Définir une fonction iterator : 'a tree -> 'a iterator_infix permettant de créer un itérateur à partir d'un arbre.
Définir une fonction next : 'a iterator_infix -> ('a * 'a iterator_infix) option.
Définir une fonction 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 :

Questions bonus

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 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) option

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

Il 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)

Définir la fonction next : 'a iterator -> ('a * 'a iterator) option.
Définir la fonction iterator : 'a tree -> 'a iterator correspondant au parcours préfixe.
Définir la fonction elements : 'a tree -> 'a list en utilisant l'itérateur et vérifier
```
let () =
  assert (elements a1 = [2; 3; 5; 6; 8; 12; 15])
       
```
Définir la fonction equal : 'a tree -> 'a tree -> bool et la tester.
Tout en gardant le même type pour 'a iterator, définir une fonction
```
iterator_infix : 'a tree -> 'a iterator
       
```
et 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 :

Parcours postfixe

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.

Définir une fonction
```
iterator_postfix : 'a tree -> 'a iterator
      
```
qui crée un itérateur par continuation pour le parcours postfixe.
On cherche maintenant à implémenter le parcours postfixe sans utiliser de continuation (comme au début du sujet pour le parcours infixe). Définir, pour cet ordre, un type
```
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 list
       
```
On vérifiera
```
let () =
  assert (elements a1 = [5; 3; 8; 15; 12; 6; 2])
       
```

Déposez votre fichier :

Parcours en largeur

Le parcours en largeur consiste à explorer d'abord la racine, puis les nœuds à distance 1 de la racine, puis ceux à distance 2, etc.

Définir un type '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 vide
- push : 'a queue -> 'a -> 'a queue : ajout d'un élément à la fin d'une file
- pop : 'a queue -> ('a * 'a queue) option : retrait du premier élément d'une file
On ne cherchera pas particulièrement à être efficace (par exemple, une implémentation simple avec 'a queue = 'a list sera acceptable).
En utilisant ces files, définissez un type d'itérateur (on pourra utiliser un type spécialisé ou des continuations) et implémentez la fonction 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 :

Une référence

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.