ENSEIRB Première année 2002/2003

Programmation Fonctionnelle : feuille 5

Structures - Tables de hachage

Exercice 5.1 Structures

1. Définir une structure point pour représenter les points du plan. Tester la fonction

make-point et le prédicat point-p.

2. Améliorer la définition de la structure en précisant une fonction d’impression et en donnant une valeur par défaut à un point.

3. On se sert de la structure point pour représenter un vecteur. On considère la relation de co-linéarité sur les vecteurs. Écrire une fonction on-the-same-line qui renvoie vrai si deux vecteurs sont colinéaires et faux sinon. Cette relation est une relation d’équivalence.

4. Utiliser la fonction set-from-list vue au TD précédent pour obtenir un ensemble de vecteurs à partir d’une liste de vecteurs.

5. En utilisant on-the-same-line et set-from-list, écrire une fonction qui, à partir d’une liste de vecteurs, construit un ensemble ne contenant qu’un représentant par classe.

Exercice 5.2 Tables de hachage Une couleur peut être considérée comme composée des couleurs rouge R, verte G et bleue B.

1. Définir une structure pour représenter une couleur.

2. Il s’agit de créer une table qui associe des noms de couleurs aux couleurs elles-mêmes. Utiliser une table de hachage dont la clé d’accès est le nom de la couleur recherchée. Utiliser la fonction describe pour examiner la table ainsi créée. Compléter la table en utilisant gethash. Tester l’ajout d’un nouvel élément dont la clé est déjà présente. Tester la suppression d’un élément de la table avec remhash.

3. En utilisant la fonction maphash, écrire une fonction qui construit la liste des clés de la table des couleurs.

4. Écrire un prédicat warm-colorp qui renvoie vrai si une couleur est une couleur chaude (taux de rouge supérieur au taux de bleu) et faux sinon.

5. Construire des exemples de manipulation d’une table de couleurs en utilisant la macro

with-hash-table-iterator. Utiliser la macro multiple-value-bind pour récupérer

les valeurs retournées pas l’itérateur fourni dans with-hash-table-iterator.

6. Utiliser ces dernières notions pour écrire une fonction qui extrait le nom des couleurs chaudes contenues dans la table.