:: Enseignements :: Licence :: L3 :: 2007-2008 :: Programmation fonctionnelle ::
[LOGO]

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

Exercice 6 - Fonctionnalités étendues

Exercice 7 - Autres implantations

  • Proposer d'autres implantations, inspirées de vos cours d'algorithmique ou du dernier partiel.