Cours 7
Cours 7
Programming, Math, etc. · course
Voir tous les documents en programmationTous les cours en programmation
Fiche de révisionFiche de cours
Rédigée à partir de ce document, puis vérifiée avant publication.
Ce cours s'adresse aux étudiants en informatique ou en programmation qui souhaitent maîtriser les listes d'association en Common Lisp ainsi que les fonctions associées pour manipuler ces structures de données. Il couvre les notions fondamentales des listes d'association, leurs opérations principales, ainsi que les fonctions de comparaison et de manipulation des clés et valeurs.
Une liste d'association (ou association list, abrégée alist) est une liste dont les éléments sont des paires (cons). Chaque paire associe une clé (stockée dans le car) à une valeur (stockée dans le cdr). Cette structure sert de table indexée simple.
Bien que peu efficace pour les grandes tables, la liste d'association est simple à utiliser, notamment grâce aux fonctions fournies par Common Lisp.
La fonction la plus fondamentale pour manipuler une liste d'association est assoc. Elle prend deux arguments : une clé et une liste d'association. Elle parcourt la liste à la recherche d'une paire dont la clé correspond à la clé donnée. Si elle trouve une telle paire, elle renvoie la paire entière ; sinon, elle renvoie nil.
(assoc 'oeuf '((eau . water) (oeuf . egg) (sel . salt)))
; Résultat : (OEUF . EGG)
Exemple avec une liste plus complexe :
(defparameter *languages*
'((symbolic . (lisp ml haskell))
(imperative . (lisp c pascal cobol fortran))
(object-oriented . (lisp c++ java))
(numeric . (lisp fortran))))
(assoc 'imperative *languages*)
; Résultat : (IMPERATIVE LISP C PASCAL COBOL FORTRAN)
(cdr (assoc 'imperative *languages*))
; Résultat : (LISP C PASCAL COBOL FORTRAN)
(assoc 'postfix *languages*)
; Résultat : NIL
Remarque : Une paire de type (a . (b ...)) est équivalente à une liste (a b ...). La fonction print affiche toujours la seconde forme, ce qui explique la différence d'affichage dans l'exemple ci-dessus.
L'expression (cdr (assoc ...)) est un idiome courant pour obtenir la valeur associée à une clé, même si la clé n'existe pas (car (cdr nil) vaut nil en Common Lisp).
Par défaut, assoc utilise le prédicat eql pour tester l'égalité des clés. Il est possible de spécifier un autre prédicat avec l'argument mot-clé :test.
(assoc "oeuf"
'(("eau" . "water") ("oeuf" . "egg") ("sel" . "salt")))
; Résultat : NIL (car "oeuf" n'est pas égal à 'oeuf)
(assoc "oeuf"
'(("eau" . "water") ("oeuf" . "egg") ("sel" . "salt"))
:test #'string-equal)
; Résultat : ("oeuf" . "egg")
Pour tester la négation d'un prédicat, on peut utiliser :test-not.
Il est aussi possible d'appliquer une fonction à la clé avant le test avec l'argument :key. Par exemple :
(assoc "oe"
'(("eau" . "water") ("oeuf" . "egg") ("sel" . "salt"))
:test #'string-equal
:key (lambda (s) (subseq s 0 2)))
; Résultat : ("oeuf" . "egg")
La fonction assoc-if est similaire à assoc, mais elle prend un prédicat en premier argument et applique ce prédicat à chaque clé jusqu'à ce qu'il renvoie vrai. Elle renvoie alors la paire correspondante.
Un argument :key peut aussi être passé.
(assoc-if
#'(lambda (s) (string-equal (subseq s 0 2) "oe"))
'(("eau" . "water") ("oeuf" . "egg") ("sel" . "salt")))
; Résultat : ("oeuf" . "egg")
La fonction assoc-if-not fonctionne de la même manière, mais utilise la négation du prédicat.
(assoc-if-not
#'(lambda (s) (> (length s) 3))
'(("eau" . "water") ("oeuf" . "egg") ("sel" . "salt")))
; Résultat : ("eau" . "water")
Pour ajouter un élément à une liste d'association, on peut utiliser cons ou push. La fonction acons crée une paire et l'ajoute en tête d'une liste d'association :
(acons 'a 1 '((b . 2) (c . 3)))
; Résultat : ((A . 1) (B . 2) (C . 3))
La fonction pairlis permet de construire une liste d'association à partir d'une liste de clés et d'une liste de valeurs.
Pour supprimer une paire, on utilise des fonctions comme remove, remove-if, remove-if-not ou leurs versions destructives delete, delete-if, delete-if-not.
Pour modifier la valeur associée à une clé, on utilise l'idiome suivant :
(setf (cdr (assoc clé liste)) nouvelle-valeur)
Ces fonctions sont similaires à assoc, assoc-if et assoc-if-not, mais elles recherchent la valeur dans le cdr au lieu de la clé dans le car. Elles inversent donc les rôles clé-valeur.
Une liste d'association étant une liste, on peut utiliser toutes les fonctions définies pour les listes et séquences, notamment find, member et position.
Pour copier une liste d'association, il faut utiliser la fonction spécialisée copy-alist.
car et cdr).assoc mais qui recherche dans les valeurs plutôt que dans les clés.assoc pour comparer les clés.assoc est centrale pour rechercher une paire selon une clé, avec possibilité de personnaliser le test d'égalité.assoc-if et assoc-if-not permettent de rechercher selon un prédicat appliqué aux clés.rassoc, rassoc-if et rassoc-if-not inversent les rôles clé-valeur dans la recherche.copy-alist pour éviter les effets de bord.