Exercice 1 : Files FIFO

On souhaite implémenter un module de file first-in first-out, avec l'interface suivante

• une solution naïve consiste à définir :

  1. type 'a t = 'a list
     

  Implémenter cette solution.

• une solution légèrement plus sophistiquée donne d'excellents résultats en pratique. Elle consiste à couper la file en deux listes : celle des éléments en début de file, et celle des éléments en fin de file dans l'ordre inverse de la file. Ainsi, les opérations push et head peuvent s'implémenter en temps constant. On gardera comme invariant que la liste des éléments en tête doit être non-vide, sauf si la file elle-même est vide. Implémenter cette solution.

• On va maintenant fournir des fonctionnelles sur notre file, en donnant un foncteur transformant un module de type MinFILE en module de type FILE :

  1. module type FILE =
     
  2. sig
     
  3. include MinFILE
     
  4. 
     
  5. val length : 'a t -> int (* le nombre d'éléments dans la file *)
     
  6. 
     
  7. (* les fonctionnelles usuelles *)
     
  8. val map : ('a -> 'b) -> 'a t -> 'b t
     
  9. val fold : ('a -> 'b -> 'a) -> 'a -> 'b t -> 'a
     
  10. val filter : ('a -> bool) -> 'a t -> 'a t
      
  11. 
      
  12. end
      

  Coder ce foncteur.

• Question facultative d'algorithmique : quelle est la complexité amortie de tail avec l'implémentation en deux listes ?

Exercice 2 : le type option

Le module Pervasive fournit un type bien utile, le type option permettant de coder une valeur optionnelle :

• coder une fonction qui filtre les options d'une liste, pour garder uniquement les valeurs définies :

  1. val option_filter : 'a option list -> 'a list
     

• quel est le type de la fonction suivante ?

  1. let (>>=) e f = match e with
     
  2. | None -> None
     
  3. | Some v -> f v
     

• Utiliser >>= pour coder une fonction prenant trois arguments de type int option, et qui renvoie une option contenant la somme des trois entiers, s'ils sont définis, ou None sinon.

• Plusieurs structures de données, par exemple Map.S, implémentent l'interface :

  1. module type ASSOC =
     
  2. sig
     
  3. type key
     
  4. type 'a t
     
  5. 
     
  6. val mem : key -> 'a t -> bool
     
  7. val find : key -> 'a t -> 'a
     
  8. end
     

  On peut combiner les mem et find en une seule fonction de type :

  1. val mem_find : key -> 'a t -> 'a option
     

  Écrire un foncteur Add_MF, qui construit automatiquement la fonction mem_find à partir d'une implémentation de ASSOC. On pourra ensuite écrire, par exemple :

  1. module SMap = Map.Make(String)
     
  2. 
     
  3. module SMap_ext =
     
  4. struct
     
  5. include SMap
     
  6. include Add_MF(SMap)
     
  7. end
     

  pour obtenir un module implémentant Map.S étendu à la fonction mem_find.

Exercice 3 : Files de priorité

On se propose d'implémenter une file de priorité (un tas) en programmation fonctionnelle. Souvenons-nous qu'un tas sur un type ordonné implémente les opérations d'insertion, et de suppression du minimum. Usuellement, l'implémentation est le tas binaire. Mais puisque nous n'avons pas le droit d'utiliser de tableau, nous allons devoir innover.

• Écrire une interface de file de priorité.

• Commençons par écrire une implémentation sur les entiers, la dernière question consistera à transformer notre code en foncteur. Nous allons utiliser le type suivant :

  1. type elt = int
     
  2. type t =
     
  3. | Empty
     
  4. | Node of elt * t list
     
  5. (* invariant : a est le plus petit élément de Node (a,lst_heap) *)
     

  Écrire les valeurs suivantes :

  1. val empty : t
     
  2. val is_empty : t -> bool
     

• La première chose à faire est d'écrire une fonction prenant deux tas, et retournant l'union de ces deux tas. Si les deux tas sont non-vides, il suffit de rajouter le tas dont le minimum est le plus grand à la liste contenue dans l'autre tas :

  1. merge (Node (15,plus_grand_que_15)) (Node (8,plus_grand_que_8)) =
     
  2. Node (8, (Node (15,plus_grand_que_15))::plus_grand_que_8)
     

  Coder la fonction merge

• Pour insérer un élément dans un tas, il suffit de créer un tas contenant seulement cet élément , puis d'utiliser merge. Coder la fonction d'insertion.

• Étant donné un tas non-vide, retourner le minimum est facile, mais il faut aussi calculer la file des éléments une fois le minimum retiré. Une solution consiste à effectuer l'opération merge sur les éléments de la liste des tas restants, jusqu'à obtenir un seul tas, à l'aide d'une fonctionnelle de liste.

• Cette première solution offre dans certains cas des performances médiocres. À la place, nous faisons les opérations de merge dans un ordre bien particulier. Si la liste de tas est $[t_1;t_2;\ldots;t_n]$ et $\oplus$ dénote l'opérateur infixe pour merge, on calcule :

  $$(t1 \oplus t2) \oplus (t3 \oplus t4) \oplus (t5 \oplus t6) \oplus \ldots \oplus \left(t_n\;\text{ou}\;(t_{n-1} \oplus t_n)\;\text{selon la parité de}\;n\right)$$

  Écrire une fonctionnelle de liste généralisant cette expression, puis l'appliquer pour obtenir l'opération de suppression du minimum.

Cette implémentation des tas porte le nom de tas par appariement. Cette implémentation simple est aussi très efficace en pratique, mais très difficile à analyser de manière théorique (il est conjecturé que la complexité amortie des opérations d'insertion et fusion est $O(1)$, mais personne n'est parvenu à le prouver). Par ailleurs, par rapport aux tas binaires, on gagne une opération de fusion qui n'est pas du tout implémentable dans les tas binaires.