Cours 7

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.

Listes d'association

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.

Fonction assoc

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).

Personnalisation du test d'égalité

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")

Fonctions assoc-if et assoc-if-not

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")

Ajout, suppression et modification d'éléments

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)

Fonctions rassoc, rassoc-if et rassoc-if-not

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.

Utilisation des fonctions sur séquences

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.

Copie d'une liste d'association

Pour copier une liste d'association, il faut utiliser la fonction spécialisée copy-alist.

Glossaire des termes clés

• Liste d'association (alist) : Liste dont les éléments sont des paires (cons) associant une clé à une valeur.
• Cons : Structure de données Lisp représentant une paire de valeurs (car et cdr).
• Car : Premier élément d'une paire cons, souvent utilisé comme clé dans une liste d'association.
• Cdr : Second élément d'une paire cons, souvent utilisé comme valeur dans une liste d'association.
• Assoc : Fonction qui recherche une paire dans une liste d'association selon une clé.
• Assoc-if : Fonction qui recherche une paire dont la clé satisfait un prédicat.
• Assoc-if-not : Fonction qui recherche une paire dont la clé ne satisfait pas un prédicat.
• Acons : Fonction qui crée une paire et l'ajoute en tête d'une liste d'association.
• Pairlis : Fonction qui construit une liste d'association à partir de deux listes (clés et valeurs).
• Rassoc : Fonction similaire à assoc mais qui recherche dans les valeurs plutôt que dans les clés.
• Test d'égalité (eql) : Prédicat par défaut utilisé par assoc pour comparer les clés.
• :test : Argument mot-clé permettant de spécifier un autre prédicat de comparaison.
• :test-not : Argument mot-clé pour utiliser la négation d'un prédicat.
• :key : Argument mot-clé permettant d'appliquer une fonction à la clé avant le test.
• Copy-alist : Fonction pour copier une liste d'association.

Points clés à retenir

• Une liste d'association est une structure simple pour associer des clés à des valeurs via des paires cons.
• La fonction 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.
• On peut ajouter, supprimer ou modifier des paires dans une liste d'association avec des fonctions spécifiques ou des idiomes Lisp.
• Les fonctions rassoc, rassoc-if et rassoc-if-not inversent les rôles clé-valeur dans la recherche.
• Une liste d'association est une liste, donc toutes les fonctions sur les listes s'appliquent.
• Pour copier une liste d'association, utiliser copy-alist pour éviter les effets de bord.