:: Enseignements :: Licence :: L3 :: 2007-2008 :: Programmation fonctionnelle ::
| Modules |
Ce TP va nous convaincre que les modules peuvent servir à définir des structures abstraites sans présager de leur implantation.
Ainsi, un dictionnaire peut être vu, indépendamment de l'implantation, comme une structure dans laquelle on veut pouvoir ranger des valeurs indexées par des clés (comme des définitions indexées par des mots dans un vrai dictionnaire).
Exercice 1 - Signature
Considérons dans un premier temps qu'un dictionnaire fait intervenir trois types (la structure elle-même, le type des clés, le type des valeurs) et quatre fonctions (création de la structure, ajout d'un élément, recherche et suppression d'un élément correspondant à une clé).
-
Écrire la signature Dico de module correspondante. On prendra le parti de fonctions par effet de bord pour l'ajout et la suppression, plutôt que par retour de la nouvelle structure.
-
Comment traiter le cas où la recherche ou la suppression ne trouvent aucun élément correspondant à la clé donnée?
Un module
D implantant cette signature devra par exemple permettre la succession de commandes suivantes:
Exercice 2 - Référence de liste
-
Écrire un module correspondant à cette signature, qui utilise une référence de liste, et avec des chaînes de caractères comme clé et des entiers comme valeur.
-
Modifier les fonctions pour toujours garder la liste triée, ce qui permet de petites optimisations.
-
Imposer le type Dico pour ce module. Quel problème apparaît lors des tests? On peut rendre public une définition de type lors du cast grâce la syntaxe "with type key=... and type value=..."
-
Utiliser ce module pour faire un tableau de correspondance entre des noms propres et des notes de partiel.
Exercice 3 - Généricité
Plus généralement, on veut pouvoir utiliser l'implantation par liste triée pour n'importe quels types de clé et de valeur.
-
Paraméter le type de la structure par le type de valeur afin de ne pas avoir à le spécifier dans le module.
-
Quel problème apparaît si l'on cherche à faire de même pour le type de clé? On va régler ce problème par un foncteur. Écrire un module définissant le type de clé comme une chaîne de caractère.
-
Transformer le module de la question précédente (par liste triée) en foncteur attendant comme argument un module qui définirait le type de clé.
-
De quelle fonction supplémentaire est caractéristique du type de clé? Adapter le module de clé.
Exercice 4 - Mémorisation d'une fonction
Le dictionnaire va maintenant servir à stocker les résultats d'une fonction afin de ne pas les recaculer.
-
Pour une fonction f : int -> int et un dictionnaire dic : Dico with type key = int, écrire une fonction qui rend toujours le même résultat que f, mais utilise le dictionnaire pour ne pas avoir à recalculer des résultats déjà connus.
-
Tester sur de grandes valeurs de la suite de Fibonacci définie naïvement: f(n)=1 si n=0 ou 1 et f(n)=f(n-1)+f(n-2) sinon.
-
Écrire une fonction qui prend en argument une fonction f : int -> int, crée un dictionnaire, puis renvoie la fonction avec "mémoire" correspondante.
Exercice 5 - Hachage
-
Une autre implantation de dictionnaire, avec des clés qui soient des noms propres, consiste à maintenir un tableau de 26 cases (une par lettre de l'alphabet).
Chaque case contient la liste des valeurs dont la clé commence par la lettre correspondante.
Écrire le module correspondant.
-
On peut généraliser ce procédé à n'importe quel type de clé, pourvu que chaque clé ait un indice de tableau associé.
Cette association s'appelle une fonction de hachage hash : key -> int.
Écrire le foncteur correspondant, qui attend comme argument un module définissant le type de clé et sa fonction de hachage.
Exercice 6 - Fonctionnalités étendues
-
Écrire un foncteur prenant en argument un module de type Dico et implantant des fonctions permettant de maintenir un tableau de correspondance entre noms propres et notes de partiel, en demandant à l'utilisateur d'entrer les noms et notes au clavier.
-
Regarder la signature de Hashtbl.S (dans la librairie standard), grâce à ocamlbrowser.
-
Adapter vos implantations pour qu'elles vérifient cette signature.
Exercice 7 - Autres implantations
-
Proposer d'autres implantations, inspirées de vos cours d'algorithmique ou du dernier partiel.
© Université de Marne-la-Vallée