Programmation Fonctionnelle, TD6

Exercice 1 : Arbres binaires

Proposer une interface pour les arbres binaires, vues au TP 6.

Exercice 2 : Files FIFO

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

module type MinFile = (* MinFile : interface minimale de file *)
sig
type 'a t (* le type des files *)
val empty : 'a t (* la file vide *)
val is_empty : 'a t -> bool (* teste si la file est vide *)
val push : 'a t -> 'a -> 'a t (* ajoute un élément en fin de file *)
val head : 'a t -> 'a (* le premier élément de la file *)
val tail : 'a t -> 'a t (* retire le premier élément de la file *)
end

une solution naïve consiste à définir :
1. type 'a t = 'a list
L'ajout d'un élément doit alors se faire en queue de la liste (ce qui est terriblement inefficace). Implémenter un module réalisant l'interface MinFile avec 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 un tel module.
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
5. val length : 'a t -> int (* le nombre d'éléments dans la file *)
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
12. end
Coder ce foncteur.

Exercice 3 : Files de priorité (pour les plus avancés)

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. Pour cela, nous nous baserons sur une structure concrête appelée tas par appariement (nous avions vu en cours d'algorithmique avancée les tas gauchers).

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

Les tas par appariement sont très efficaces en pratique, mais très difficiles à 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).