Listes d'association

Une liste d'association (en Anglais : association list, ou alist) est une liste dont les éléments sont des paires (cons). L'intention est que le car de chaque paire soit une clé pour nommer l'objet dans le cdr de la paire. Une liste d'association est donc une table indexée.

Une liste d'association n'est certainement pas la façon la plus efficace de construire une table indexée. Mais pour des tables de petite taille, c'est une méthode simple car Common Lisp fournit plusieurs fonctions permettant de la manipuler.

La fonction la plus fondamentale pour la manipulation de listes d'association est assoc. Cette fonction prend deux paramètres, une clé et une liste d'association. La liste est parcourue à la recherche d'une paire dont la clé (le car) corresponde à la clé donnée en argument. Si une telle clé est trouvée, la paire entière est renvoyée. Sinon, nil est renvoyé. Exemples :

* (assoc 'oeuf '((eau . water) (oeuf . egg) (sel . salt)))

(OEUF . EGG)
* (defparameter *languages*
    '((symbolic . (lisp ml haskell))
      (imperative . (lisp c pascal cobol fortran))
      (object-oriented . (lisp c++ java))
      (numeric . (lisp fortran))))

*LANGUAGES*
* (assoc 'imperative *languages*)

(IMPERATIVE LISP C PASCAL COBOL FORTRAN)
* (cdr (assoc 'imperative *languages*))

(LISP C PASCAL COBOL FORTRAN)
* (assoc 'postfix *languages*)

NIL
*

Remarques : Une paire de type (a . (b ...)) (i.e., dont le cdr est une liste) est la même chose qu'une liste (a b ...). La fonction print utilise toujours la deuxième syntaxe. C'est pourquoi le résultat de l'expression (assoc 'imperative *languages*) est affiché différemment de la façon dont il a été tapé. L'expression (cdr (assoc ...)) qui permet d'obtenir la valeur sans la clé est un idiome Common Lisp. Ça fonctionne même si il n'y a pas de paire correspodant à la clé, car en Common Lisp la valeur de l'expression (cdr nil) est nil.

Le prédicat pour tester l'équivalence entre deux clés est eql par défaut. Un autre prédicat peut être choisi grâce à un argument mot-clé8.1 :test. Exemple :

* (assoc "oeuf"
         '(("eau" . "water") ("oeuf" . "egg") ("sel" . "salt")))

NIL
* (assoc "oeuf"
         '(("eau" . "water") ("oeuf" . "egg") ("sel" . "salt"))
         :test #'string-equal)

("oeuf" . "egg")
*

Pour éviter un test avec négation, l'argument mot-clé :test-not peut également être utilisé.

Il est possible d'appliquer une fonction arbitraire à la clé avant d'effectuer le test. Pour cela, il faut utiliser un arguement mot-clé :key. Exemple :

* (assoc "oe"
         '(("eau" . "water") ("oeuf" . "egg") ("sel" . "salt"))
         :test #'string-equal :key (lambda (s) (subseq s 0 2)))

("oeuf" . "egg")
*

La fonction assoc-if est similaire à assoc. Elle prend deux paramètres obligatoires, un prédicat et une liste d'association. Le prédicat est appliqué à la clé de chaque paire de la liste jusqu'à ce que le prédicat renvoie vrai. La paire correspondante est alors renvoyée comme résultat de l'appel à assoc-if. Un argument mot-clé :key peut également être passé comme pour assoc. La fonction assoc-if-not est similaire à assoc-if, mis à part que c'est la négation du prédicat qui est utilisée. Exemples :

* (assoc-if
   #'(lambda (s) (string-equal (subseq s 0 2) "oe"))
   '(("eau" . "water") ("oeuf" . "egg") ("sel" . "salt")))

("oeuf" . "egg")
* (assoc-if-not
   #'(lambda (s) (> (length s) 3))
   '(("eau" . "water") ("oeuf" . "egg") ("sel" . "salt")))

("eau" . "water")
*

Pour ajouter un élément à une liste d'association, il est bien sûr possible d'utiliser cons ou push. La fonction acons permet de créer une paire et de la ``conser'' au début d'une liste d'association simultanément :

* (acons 'a 1 '((b . 2) (c . 3)))

((A . 1) (B . 2) (C . 3))
*

Il est également possible d'utiliser pairlis permettant de construire une liste d'association à partir d'une liste de clés et d'une liste de valeurs.

Pour supprimer une paire dans une liste d'association, utiliser une fonction comme remove, remove-if ou remove-if-not (ou les versions destructives correspondantes delete, delete-if et delete-if-not).

Pour changer la valeur d'une clé dans une liste d'association, utiliser l'idiome (setf (cdr (assoc ...)) expr).

Les trois fonctions rassoc, rassoc-if et rassoc-if-not fonctionnent comme assoc, assoc-if et assoc-if-not mais avec les rôles clé-valeur inversés.

Puisque une liste d'association est une liste et une liste, une séquence, il est également possible d'utiliser l'ensemble des fonctions définies pour les listes et les séquences sur les listes d'association. En particulier, les fonctions find, member et position.

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

Irene DURAND
2011-10-14