Programmation fonctionnelle : TP7
Arbres de préfixe comme ensembles
Implanter les arbres de préfixes tels que vus en cours.
Chaque fonction devra être commentée ; écrivez le type avant de
coder !
On codera les fonctions :
- Cardinal,
- Nombre de lettres contenues,
- Taille du mot le plus long,
- Ajout, dans un premier temps naïvement, dans un deuxième temps
en levant une exception quand on essaie d'ajouter un élément déjà présent,
- Union de deux arbres de préfixe.
- Terminaisons : qui retourne la liste des mots contenus dans un
trie en fonction d'un préfixe passé en paramètre.
- Liste_mots : qui retourne la liste de tous les mots contenus dans
un trie.
Arbres de préfixes comme structures d'associations
Reprendre les questions de l'exercice précédent mais cette fois la
structure est une structure d'association. Coder en particulier une
fonction find qui sur la donnée d'une clef chaînée retourne
l'élément associé s'il existe et l'exception Not_found sinon.
Un peu plus loin
On peut utiliser des arbres de préfixes pour représenter les
dictionnaires des téléphones portatifs proposant un mode T9. Dans ce
mode, des mots sont proposés lorsqu'ils correspondent à des
séquences de touches ; plusieurs mots pouvant convenir pour une
séquence donnée.
- Proposer une modification du type des arbres de préfixes vus
en cours afin de les utiliser pour un mode T9.
- Coder une fonction mots qui sur la donnée d'une
séquence de chiffres retourne la liste des mots du dictionnaire
correspondants.