Paires et alists

Les listes associatives, ou alists pour association lists, permettent d’associer des clés à des valeurs. Les applications sont multiples. On peut par exemple avoir une alist qui à des noms de compositeurs associe leurs dates de naissances. LilyPond possède une alist qui associe à une langue de saisie des notes (comme \language "français") les noms des notes qui lui appartiennent. Ces noms sont eux-mêmes construits comme une alist qui à un nom associe une hauteur. Une autre alist associe des altérations aux glyphes de la police Feta. Bref, les alists sont partout.

Un mot sur les paires

Les alists sont fondées sur les paires. Celles-ci sont des objets un peu particuliers, qui associent exactement deux éléments, au contraire des listes qui en associent autant que besoin. Comme avec les listes, il y a deux méthodes pour créer une paire :

(cons élément1 élément2)

ou

'(élément1 . élément1)

La première consiste à appeler la fonction cons, dont le nom est une abréviation de « construct ». Naturellement, elle prend deux arguments. La seconde est une forme de quoting, où le point entre les deux éléments indique qu’il s’agit d’une paire et non d’une liste. L’interpréteur affiche les paires exactement comme des listes, mais en rajoutant ce point central.

(cons 1 2)
⇒ (1 . 2)

Les espaces autour du point ont leur importance. '(1 . 2) est une paire, alors que '(1.2) est une liste à un seul élément qui est le nombre « un virgule deux ».

La technique du quasiquoting fonctionne aussi pour les paires.

(define naissance 1756)
`(âge . ,(- 2021 naissance))
⇒ (âge . 265)

On accède aux éléments d’une paire à l’aide des fonctions car et cdr.

(car '(1 . 2))
⇒ 1
(cdr '(1 . 2))
⇒ 2

On peut regretter que les noms « car » et « cdr » ne soient pas très explicites. Ce sont en fait des acronymes techniques qui proviennent des premières implémentations du langage Lisp, l’ancêtre de Scheme (« car » et « cdr » signifieraient « Contents of the Address part of the Register » et « Contents of the Decrement part of the Register »).

Alists

Une alist n’est rien d’autre qu’une liste de paires. Le car de chaque paire est une clé, et le cdr est la valeur associée à cette clé. Les clés sont de préférence uniques, c’est à dire qu’il n’y a pas deux paires dans l’alist avec le même car. Cependant, il existe des cas légitimes où l’on peut se dégager de cette règle.

Voici une première alist :

(define dates-naissance
  '(("Mozart" . 1756)
    ("Beethoven" . 1778)
    ("Schumann" . 1810)
    ("Hába" . 1893)
    ("Weill" . 1900)
    ("Ligeti" . 1923)))

Guile (rappel : l’implémentation de Scheme utilisée par LilyPond) possède une panoplie de fonctions dédiées aux alists.

Accès à une valeur

D’abord, celles pour trouver la valeur associée à une clé. Il en existe non pas une mais six, avec des différences. Elles se classent en deux familles :

• assq, assv, assoc,

• assq-ref, assv-ref, assoc-ref.

Les fonctions de la première famille, sur l’exemple de assoc, s’emploient comme ceci :

(assoc clé alist)

La valeur de retour est la paire (clé . valeur), si elle existe dans l’alist, et le booléen #f sinon.

Quant aux fonctions de la deuxième famille, détail ennuyeux, elles s’appellent avec les arguments dans l’ordre inverse :

(assoc-ref alist clé)

La valeur de retour est l’élément valeur de la paire (clé . valeur), si elle existe dans l’alist, et le booléen #f sinon.

Entre les fonctions d’une même famille, la différence réside dans la méthode de comparaison des clés. Toutes ces fonctions commencent par regarder la première paire dans l’alist, comparent son car à la clé recherchée, et renvoient le cdr si la clé est la bonne, sinon regardent la deuxième paire, etc. Il faut donc une fonction pour comparer la clé voulue aux clés dans l’alist. Les fonctions assq et assq-ref utilisent eq?. Les fonctions assoc et assoc-ref utilisent equal?. Quant à assv et assv-ref, elle font appel à eqv?, un troisième prédicat beaucoup moins courant, qui pour faire simple sait comparer les nombres et les caractères (mais pas les chaînes de caractères).

Aussi, si les clés de l’alist sont des symboles, on se servira de assq ou assq-ref. Dans le cas général, plutôt assoc et assoc-ref.

Notre alist de dates de naissances ayant des chaînes de caractères pour clés, nous allons employer assoc et assoc-ref.

(assoc "Schumann" dates-naissance)
⇒ ("Schumann" . 1810)
(assoc-ref dates-naissance "Schumann")
⇒ 1810
(assoc-ref dates-naissance "Bartók") ; pas dans l'alist
⇒ #f

La fonction assoc-ref est clairement la plus pratique. Avec assoc, il faut prendre soi-même le cdr de la paire renvoyée. Quel est donc l’intérêt de assoc ? Il apparaît lorsque l’alist contient des valeurs égales à #f. Reprenons nos compositeurs et considérons l’alist qui associe à chacun un booléen disant si ses parents étaient musiciens (au moins l’un des deux).

(define parents-musiciens
  '(("Mozart" . #t)
    ("Beethoven" . #t)
    ("Schumann" . #f)
    ("Weill" . #t)))
(assoc-ref parents-musiciens "Mozart")
⇒ #t
(assoc-ref parents-musiciens "Bach")
⇒ #f

assoc-ref renvoie #f pour les clés non trouvées dans l’alist. En l’occurrence, on ne peut pas distinguer si Bach n’avait pas de parent musicien ou s’il n’était tout simplement pas dans l’alist. C’est assoc qui permet de faire la différence :

(assoc "Mozart" parents-musiciens)
⇒ ("Mozart" . #t)
(assoc "Bach" parents-musiciens)
⇒ #f

Si Bach avait été dans l’alist, le résultat de assoc aurait été une paire. Cette fois-ci, #f n’est pas ambigu.

Avec assoc-ref ou une fonction de la même famille, il est courant d’exploiter la propriété que toute valeur est considérée comme vraie sauf #f pour donner une valeur par défaut grâce à or (cf. De la vérité universelle).

(or (assoc-ref dates-naissance "Bach")
    "date de naissance inconnue")
⇒ "date de naissance inconnue"

Avec assoc, il faut stocker la paire dans une variable :

(let ((paire (assoc "Bach" parents-musiciens)))
  (if paire
      (cdr paire)
      "pas d'entrée pour ce compositeur"))
⇒ "pas d'entrée pour ce compositeur"

Sachez que LilyPond définit une fonction spéciale, assoc-get. Comme assoc et assoc-ref, elle utilise equal? pour tester l’égalité des clés. Comme assoc-ref, elle renvoie la valeur associée à une clé, et pas la paire (clé . valeur). Elle prend ses arguments dans l’ordre de assoc, à savoir la clé, puis l’alist. Enfin, le troisième paramètre de assoc-get, qui est facultatif, permet de spécifier une valeur autre que #f qui sera renvoyée lorsque la clé n’est pas trouvée.

(assoc-get "Bach" parents-musiciens "pas d'entrée pour ce compositeur")
⇒ "pas d'entrée pour ce compositeur"

Modification d’une valeur

Les fonctions assq-set!, assv-set! et assoc-set! permettent de modifier la valeur associées à une clé d’une alist. Comme assq-ref, assv-ref et assoc-ref, elles emploient respectivement les prédicats eq?, eqv? et equal? pour tester l’égalité des clés. Elles s’appellent de la manière suivante :

(assxxx-set! alist clé valeur)

Elles renvoient une nouvelle alist.

(define dates-naissance
  '(("Mozart" . 1756)
    ("Beethoven" . 1778)
    ("Schumann" . 1810)
    ("Hába" . 1893)
    ("Weill" . 1900)
    ("Ligeti" . 1923)))
(assoc-set! dates-naissance "Schönberg" 1874)
⇒ (("Schönberg" . 1874) ("Mozart" . 1756) ("Beethoven" . 1778) ("Schumann" . 1810) ("Hába" . 1893) ("Weill" . 1900) ("Ligeti" . 1923))
(assoc-set! dates-naissance "Weill" 1901) ; trichons avec l'histoire
⇒ (("Mozart" . 1756) ("Beethoven" . 1778) ("Schumann" . 1810) ("Hába" . 1893) ("Weill" . 1901) ("Ligeti" . 1923))

Le point d’exclamation à la fin du nom de ces fonctions signifie qu’elles sont autorisées à modifier le contenu de l’alist en place, c’est à dire en mutant l’alist de manière à ce que dates-naissance après le premier assoc-set! contienne une nouvelle clé. Cependant, elles n’y sont pas tenues. Il faut donc systématiquement récupérer la nouvelle alist renvoyée par assxxx-set! et travailler dessus.

Il existe également acons, une fonction faite pour ajouter une entrée à une alist qui ne contient pas déjà la clé, ou bien pour les cas où les clés répétées dans l’alist ne poseraient pas problème. acons ajoute simplement une nouvelle paire au début de l’alist. Cette fois-ci, l’ordre des arguments est différent :

(acons clé valeur alist)

Par exemple :

(acons "Weill" 1901 dates-naissance)
⇒ (("Weill" . 1901) ("Mozart" . 1756) ("Beethoven" . 1778) ("Schumann" . 1810) ("Hába" . 1893) ("Weill" . 1900) ("Ligeti" . 1923))