Une liste d'associations est une liste dont chaque terme est une
association clef-valeur: chaque terme de la liste d'associations est
un couple (c'est-à-dire un n-uplet ayant deux éléments) dont le
premier élément est la clef et le second la valeur. Ainsi, étant
donnés deux types --
Clef et
Valeur -- une association
est un élément de type
NUPLET[Clef Valeur] et une liste
d'associations est un élément de type
LISTE[NUPLET[Clef
Valeur]].
Voici un exemple d'association:
;;;
(list 1 "un")
(à 1, on associe ``un'', ou encore la clef est 1 et la valeur est ``un'').
Un exemple d'une liste d'associations:
;;;
;;;
(list (list 1 "un") (list 2 "deux") (list 3 "trois"))
(à 1, on associe ``un'', à 2, on associe ``deux'', à 3, on associe ``trois'')
La fonction
ajout ajoute un couple
á cle,
valeurñ à
une liste d'associations donnée. Par exemple:
(ajout 3 "trois" (list)) ->
((3 "trois"))
(ajout 1 "un" (ajout 2 "deux"
(ajout 3 "trois" (list))))
-->
((1 "un") (2 "deux") (3 "trois"))
(let* ((L1 (ajout 3 "trois" (list)))
(L2 (ajout 2 "deux" L1))
(ma-L (ajout 1 "un" L2)))
(ajout 2 "two" ma-L))
-->
((2 "two") (1 "un") (2 "deux") (3 "trois"))
elle peut être définie par:
;;;
;;;
;;;
(define (ajout clef valeur a-liste)
(cons (list clef valeur)
a-liste))
La fonction de recherche dans une liste d'associations est une
primitive de Scheme, qui a pour nom
assoc. Son objectif est de
rechercher la première association de la liste qui a une clef donnée.
Notons que, pour des raisons d'efficacité, l'ajout d'une nouvelle
association se fait en tête de liste. Du coup, lors d'une recherche,
on rend toujours l'association la plus récente pour une clef
donnée.
C'est un semi-prédicat: elle rend #f lorsqu'une telle
association n'existe pas, et lorsqu'elle existe, elle rend la valeur
« vrai » sous une forme plus informative, à savoir l'association
elle-même:
- lorsque la clef n'existe pas:
(assoc 2 (ajout 3 "trois" (list)))
-->
#f
- lorsque la clef existe une fois:
(let* ((L1 (ajout 3 "trois" (list)))
(L2 (ajout 2 "deux" L1))
(ma-L (ajout 1 "un" L2)))
(assoc 2 ma-L))
-->
(2 "deux")
- lorsque la clef existe plusieurs fois:
(let* ((L1 (ajout 3 "trois" (list)))
(L2 (ajout 2 "deux" L1))
(ma-L (ajout 1 "un" L2)))
(assoc 2 (ajout 2 "two" ma-L)))
-->
(2 "two")
Rappelons que
assoc est une primitive de Scheme. Elle pourrait
être définie par:
;;;
;;;
;;;
(define (assoc clef aliste)
(if (pair? aliste)
(if (equal? clef (caar aliste))
(car aliste)
(assoc clef (cdr aliste)))
#f))
On peut aussi vouloir définir la fonction
valeur-de qui donne
la valeur associée à une clef. Par exemple:
(valeur-de 2 (ajout 3 "trois" (list))) ->
#F
(let* ((L1 (ajout 3 "trois" (list)))
(L2 (ajout 2 "deux" L1))
(ma-L (ajout 1 "un" L2)))
(valeur-de 2 ma-L))
-->
"deux"
Cette fonction peut être définie par:
;;;
;;;
;;;
(define (valeur-de clef aliste)
(let ((couple (assoc clef aliste)))
(if couple
(cadr couple)
#f)))
Rappel: dans une forme conditionnelle, toute condition qui n'a
pas la valeur
#f a une valeur de vérité Vrai.
Un dictionnaire français-anglais permet de traduire une phrase française (vue
comme une suite de mots) en anglais. Il peut être implanté par une
liste d'association:
(("chat" "cat") ("chien" "dog") ("souris" "mouse"))
Le problème est alors de traduire (mot à mot) une phrase française
(implantée par une liste de mots) en anglais:
(let ((mon-dico (list (list "chat" "cat")
(list "chien" "dog")
(list "souris" "mouse")
(list "manger" "eat")
(list "fromage" "cheese")))
(phr1 (list "souris" "manger" "fromage"))
(phr2 (list "chat" "manger" "souris")))
(write (traduction mon-dico phr1))
(write (traduction mon-dico phr2)))
-->
("mouse" "eat" "cheese")("cat" "eat" "mouse")
Avant d'écrire la fonction
traduction, on peut écrire des
fonctions plus simples. Par exemple,
dico-french rend la liste
des mots français du dictionnaire donné:
(let ((mon-dico (list (list "chat" "cat")
(list "chien" "dog")
(list "souris" "mouse"))))
(dico-french mon-dico))
-->
("chat" "chien" "souris")
Cette fonction se définit facilement avec un
map:
;;;
;;;
;;;
;;;
(define (dico-french dico)
(map car dico))
Pour définir la fonction
dico-anglais qui permet de
connaître la liste des mots anglais présents dans un dictionnaire,
on peut aussi utiliser un
map:
;;;
;;;
;;;
;;;
(define (dico-anglais dico)
(map cadr mon-dico))
Écrivons maintenant la fonction
traduction. Il suffit de
faire un
map avec la fonction qui traduit un mot. Cette
dernière est essentiellement la fonction
valeur-de que nous
avons définie plus haut, le seul problème étant que cette
dernière a un argument de trop (le dictionnaire). Pour résoudre ce (petit)
problème, il suffit de définir une fonction interne à la définition de
la fonction
traduction:
;;;
;;;
;;;
;;;
;;;
(define (traduction dico phrase)
(define (traduction-mot m)
(valeur-de m dico))
(map traduction-mot phrase))
