Ассоциативные списки

Ассоциативный список, или кратко alist, задаёт соответствие между ключами и значениями. Это список конс-ячеек, называемых ассоциациями: CAR каждой конс-ячейки — это ключ, а CDR — связанное значение.

Вот пример alist. Ключ pine связан со значением cones; ключ oak связан с acorns; а ключ maple связан с seeds.

((pine . cones)
 (oak . acorns)
 (maple . seeds))

И значения, и ключи в alist могут быть любыми объектами Lisp. Например, в следующем alist символ a связан с числом 1, а строка "b" связана со списком (2 3), который является CDR элемента alist:

((a . 1) ("b" 2 3))

Иногда лучше устроить alist так, чтобы связанное значение хранилось в CAR от CDR элемента. Вот пример такого alist:

((rose red) (lily white) (buttercup yellow))

Здесь мы рассматриваем red как значение, связанное с rose. Одно из преимуществ такого типа alist состоит в том, что в CDR от CDR можно хранить другую связанную информацию — даже список других элементов. Недостаток в том, что нельзя использовать rassq (см. ниже), чтобы найти элемент, содержащий заданное значение. Если ни одно из этих соображений не имеет значения, выбор зависит от вкуса, главное — придерживаться его для каждого конкретного alist.

Приведённый выше alist можно также рассматривать как список, в котором связанное значение находится в CDR элемента; значением, связанным с rose, будет список (red).

Ассоциативные списки часто используются для хранения информации, которую иначе можно было бы хранить в стеке, поскольку новые ассоциации легко добавлять в начало списка. При поиске в ассоциативном списке ассоциации с заданным ключом возвращается первая найденная, если таких ассоциаций несколько.

В Emacs Lisp не считается ошибкой, если элемент ассоциативного списка не является конс-ячейкой. Функции поиска в alist просто игнорируют такие элементы. Во многих других вариантах Lisp в таких случаях выдаётся ошибка.

Обратите внимание, что списки свойств во многом похожи на ассоциативные списки. Список свойств ведёт себя как ассоциативный список, в котором каждый ключ может встречаться только один раз. Сравнение списков свойств и ассоциативных списков см. в разделе Списки свойств.

Функция: assoc key alist &optional testfn

Эта функция возвращает первую ассоциацию для key в alist, сравнивая key с элементами alist с помощью testfn, если это функция, и equal в противном случае (см. раздел Предикаты равенства). Если testfn — функция, она вызывается с двумя аргументами: CAR элемента из alist и key. Если в alist нет ассоциации, у которой CAR равен key согласно проверке с помощью testfn, функция возвращает nil. Например:

(setq trees '((pine . cones) (oak . acorns) (maple . seeds)))
     ⇒ ((pine . cones) (oak . acorns) (maple . seeds))
(assoc 'oak trees)
     ⇒ (oak . acorns)
(cdr (assoc 'oak trees))
     ⇒ acorns
(assoc 'birch trees)
     ⇒ nil

Вот ещё один пример, в котором ключи и значения не являются символами:

(setq needles-per-cluster
      '((2 "Austrian Pine" "Red Pine")
        (3 "Pitch Pine")
        (5 "White Pine")))

(cdr (assoc 3 needles-per-cluster))
     ⇒ ("Pitch Pine")
(cdr (assoc 2 needles-per-cluster))
     ⇒ ("Austrian Pine" "Red Pine")

Функция assoc-string очень похожа на assoc, но игнорирует некоторые различия между строками. См. раздел Сравнение символов и строк.

Функция: rassoc value alist

Эта функция возвращает первую ассоциацию со значением value в alist. Если в alist нет ассоциации, у которой CDR equal значению value, она возвращает nil.

rassoc похожа на assoc, но сравнивает CDR каждой ассоциации из alist вместо CAR. Это можно считать обратной операцией assoc: она находит ключ для заданного значения.

Функция: assq key alist

Эта функция похожа на assoc: она возвращает первую ассоциацию для key в alist, но сравнение выполняется с помощью eq. Если в alist нет ассоциации, у которой CAR eq ключу key, assq возвращает nil. Эта функция используется чаще, чем assoc, поскольку eq быстрее, чем equal, а в большинстве alist в качестве ключей используются символы. См. раздел Предикаты равенства.

(setq trees '((pine . cones) (oak . acorns) (maple . seeds)))
     ⇒ ((pine . cones) (oak . acorns) (maple . seeds))
(assq 'pine trees)
     ⇒ (pine . cones)

С другой стороны, assq обычно бесполезна в alist, где ключи могут быть не символами:

(setq leaves
      '(("simple leaves" . oak)
        ("compound leaves" . horsechestnut)))

(assq "simple leaves" leaves)
     ⇒ Unspecified; might be nil or ("simple leaves" . oak).
(assoc "simple leaves" leaves)
     ⇒ ("simple leaves" . oak)

Функция: alist-get key alist &optional default remove testfn

Эта функция похожа на assq. Она находит первую ассоциацию (key . value), сравнивая key с элементами alist, и, если ассоциация найдена, возвращает её value. Если ассоциация не найдена, функция возвращает default. Для сравнения key с элементами alist используется функция, заданная в testfn; по умолчанию используется eq.

Это обобщённая переменная (см. раздел Обобщённые переменные), с помощью которой можно изменить значение посредством setf. При использовании для присваивания значения необязательный аргумент remove, отличный от nil, означает, что ассоциация key будет удалена из alist, если новое значение eql значению default.

Функция: rassq value alist

Эта функция возвращает первую ассоциацию со значением value в alist. Если в alist нет ассоциации, у которой CDR eq значению value, она возвращает nil.

rassq похожа на assq, но сравнивает CDR каждой ассоциации из alist вместо CAR. Это можно считать обратной операцией assq: она находит ключ для заданного значения.

Например:

(setq trees '((pine . cones) (oak . acorns) (maple . seeds)))

(rassq 'acorns trees)
     ⇒ (oak . acorns)
(rassq 'spores trees)
     ⇒ nil

rassq не может найти значение, хранящееся в CAR от CDR элемента:

(setq colors '((rose red) (lily white) (buttercup yellow)))

(rassq 'white colors)
     ⇒ nil

В этом случае CDR ассоциации (lily white) — это не символ white, а список (white). Это становится понятнее, если записать ассоциацию в виде пары с точечной нотацией:

(lily white) ≡ (lily . (white))

Функция: assoc-default key alist &optional test default

Эта функция ищет в alist совпадение для key. Для каждого элемента alist она сравнивает с key сам элемент (если это атом) или CAR элемента (если это конс-ячейка), вызывая test с двумя аргументами: элементом или его CAR и key. Аргументы передаются в таком порядке, чтобы можно было получить полезные результаты при использовании string-match с alist, содержащим регулярные выражения (см. раздел Поиск по регулярным выражениям). Если test не задан или равен nil, для сравнения используется equal.

Если элемент alist совпадает с key по этому критерию, assoc-default возвращает значение, определяемое этим элементом. Если элемент — конс-ячейка, возвращаемым значением будет CDR элемента. В противном случае возвращаемым значением будет default.

Если ни один элемент alist не совпадает с key, assoc-default возвращает nil.

Функция: copy-alist alist

Эта функция возвращает копию alist глубиной в два уровня: она создаёт новую копию каждой ассоциации, чтобы можно было изменять ассоциации нового alist, не меняя старый.

(setq needles-per-cluster
      '((2 . ("Austrian Pine" "Red Pine"))
        (3 . ("Pitch Pine"))

        (5 . ("White Pine"))))
⇒
((2 "Austrian Pine" "Red Pine")
 (3 "Pitch Pine")
 (5 "White Pine"))

(setq copy (copy-alist needles-per-cluster))
⇒
((2 "Austrian Pine" "Red Pine")
 (3 "Pitch Pine")
 (5 "White Pine"))

(eq needles-per-cluster copy)
     ⇒ nil
(equal needles-per-cluster copy)
     ⇒ t
(eq (car needles-per-cluster) (car copy))
     ⇒ nil
(cdr (car (cdr needles-per-cluster)))
     ⇒ ("Pitch Pine")

(eq (cdr (car (cdr needles-per-cluster)))
    (cdr (car (cdr copy))))
     ⇒ t

Этот пример показывает, как copy-alist позволяет изменять ассоциации одной копии, не затрагивая другую:

(setcdr (assq 3 copy) '("Martian Vacuum Pine"))
(cdr (assq 3 needles-per-cluster))
     ⇒ ("Pitch Pine")

Функция: assq-delete-all key alist

Эта функция удаляет из alist все элементы, у которых CAR eq ключу key, примерно так же, как если бы для удаления каждого такого элемента по отдельности использовалась delq. Она возвращает сокращённый alist и часто изменяет исходную структуру списка alist. Для получения правильного результата используйте возвращаемое значение assq-delete-all, а не сохранённое значение alist.

(setq alist (list '(foo 1) '(bar 2) '(foo 3) '(lose 4)))
     ⇒ ((foo 1) (bar 2) (foo 3) (lose 4))
(assq-delete-all 'foo alist)
     ⇒ ((bar 2) (lose 4))
alist
     ⇒ ((foo 1) (bar 2) (lose 4))

Функция: assoc-delete-all key alist &optional test

Эта функция похожа на assq-delete-all, но принимает необязательный аргумент test — функцию-предикат для сравнения ключей в alist. Если аргумент не задан или равен nil, по умолчанию для test используется equal. Как и assq-delete-all, эта функция часто изменяет исходную структуру списка alist.

Функция: rassq-delete-all value alist

Эта функция удаляет из alist все элементы, у которых CDR eq значению value. Она возвращает сокращённый alist и часто изменяет исходную структуру списка alist. rassq-delete-all похожа на assq-delete-all, но сравнивает CDR каждой ассоциации из alist вместо CAR.

Макрос: let-alist alist body

Создаёт привязку для каждого символа, используемого в качестве ключа в ассоциативном списке alist, добавляя перед ним точку. Это может быть полезно при обращении к нескольким элементам одного ассоциативного списка; принцип лучше всего виден на простом примере:

(setq colors '((rose . red) (lily . white) (buttercup . yellow)))
(let-alist colors
  (if (eq .rose 'red)
      .lily))
     ⇒ white

Во время раскрытия макроса анализируется body, и привязки создаются для символов, которые буквально встречаются в body и начинаются с ‘.’. Поиск ключей выполняется с помощью assq, а cdr возвращаемого значения этого assq присваивается в качестве значения привязки. Сгенерированный код выполняет все обращения к alist до любой другой части body, поэтому символ .foo, где бы он ни встречался в body, будет найден (с использованием ключа foo) и привязан независимо от того, используется ли он фактически в body во время выполнения.

Поддерживаются вложенные ассоциативные списки:

(setq colors '((rose . red) (lily (belladonna . yellow) (brindisi . pink))))
(let-alist colors
  (if (eq .rose 'red)
      .lily.belladonna))
     ⇒ yellow

Вложение let-alist друг в друга допускается, но код во внутреннем let-alist не может обращаться к переменным, привязанным внешним let-alist.

Поддерживается также индексация списков:

(setq colors '((rose . red) (lily . (yellow pink))))
(let-alist colors .lily.1)
     ⇒ pink

Обратите внимание: формы вроде ‘.0’ или ‘.3’ интерпретируются как числа, а не как символы, поэтому они не будут привязаны к соответствующим значениям в alist.