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

Ассоциативный список, или a-list, является структурой данных, часто используемой в Lisp’е. a-list является списком пар (cons-ячеек). Каждая пара является ассоциацией. car элемент пары называется key, и cdr элемент datum.

Преимущество a-list представления данных в том, что a-list может быть постепенно увеличен путём простого добавления в начало новых записей. Кроме того, поскольку функция поиска assoc по порядку проходит элементы a-list, то новые записи могут «скрыть» старые. Если a-list рассматривать как отображение ключей в значения, то отображение может быть не только увеличено, но также изменено с помощью добавления новых записей в начало a-list.

Иногда a-list представляет биективное (bijective) отображение, и бывает нужно получить ключ для некоторого значения. Для этих целей используется функция «реверсивного» поиска rassoc. Другие варианты поиска в a-list могут быть созданы с помощью функции find или member.

Допустимо, чтобы nil был элемент a-list вместо пары ключ-значение. Такой элемент не считается парой и просто пропускается при использовании функции assoc.

[Функция] acons key datum a-list

acons создаёт новый ассоциативный список, с помощью добавления пары (key . datum) к старому a-list.

(acons x y a) ≡ (cons (cons x y) a)

[Функция] pairlis keys data &optional a-list

pairlis принимает два списка и создаёт ассоциативный список, который связывает элементы первого списка с соответствующими элементами второго. Если списки не одинаковой длины, это является ошибкой. Если указан необязательный аргумент a-list, тогда новые пары добавляются к нему в начало.

Новые пары могут быть расположены в итоговом списке a-list в любом порядке. Например:

(pairlis ’(one two) ’(1 2) ’((three . 3) (four . 19)))

может быть

((one . 1) (two . 2) (three . 3) (four . 19))

или может быть так

((two . 2) (one . 1) (three . 3) (four . 19))

[Функция] assoc item a-list &key :test :test-not :key
[Функция] assoc-if predicate a-list &key :key
[Функция] assoc-if-not predicate a-list &key :key

Каждая из этих функций осуществляет поиск в ассоциативном списке a-list. Функция возвращает первую пару, удовлетворяющую условию, или nil, если такой пары не было найдено. Например:

(assoc ’r ’((a . b) (c . d) (r . x) (s . y) (r . z)))
         ⇒ (r . x)
(assoc ’goo ’((foo . bar) (zoo . goo))) ⇒ nil
(assoc ’2 ’((1 a b c) (2 b c d) (-7 x y z))) ⇒ (2 b c d)

Если функция вернула пару, можно изменить её значение с помощью rplacd. (Однако лучше будет добавить новую «затеняющую» пару в начало, чем модифицировать старую.) Например:

(setq values ’((x . 100) (y . 200) (z . 50)))
(assoc ’y values) ⇒ (y . 200)
(rplacd (assoc ’y values) 201)
(assoc ’y values) ⇒ (y . 201) теперь

Типичный приём использования (cdr (assoc x y)). Так как cdr от nil гарантировано вычисляется в nil, то в случае отсутствия нужной пары, будет возвращено значение nil. nil также будет возвращено, если значение для ключа равно nil. Такое поведение удобно, если nil несёт смысл «значения по-умолчанию».

Два выражения

(assoc item list :test fn)

и

(find item list :test fn :key #’car)

эквивалентны за исключением, того что assoc игнорирует значения nil на месте пар.

Смотрите также find и position.

X3J13 voted in January 1989 to restrict user side effects; see section 7.9.

Пользователь ограничен в создании побочных действий так, как это описано в разделе 7.9

[Функция] rassoc item a-list &key :test :test-not :key
[Функция] rassoc-if predicate a-list &key :key
[Функция] rassoc-if-not predicate a-list &key :key

rassoc является реверсивной формой для assoc. Функция ищет пары, у которых cdr элемент удовлетворяет заданному условию. Если a-list рассматривается как отображение, то rassoc обрабатывает a-list как представление инверсного отображения. Например:

(rassoc ’a ’((a . b) (b . c) (c . a) (z . a))) ⇒ (c . a)

Выражения

(rassoc item list :test fn)

и

(find item list :test fn :key #’cdr)

эквивалентны за исключением, того что rassoc игнорирует значения nil на месте пар.

X3J13 voted in January 1989 to restrict user side effects; see section 7.9.

Пользователь ограничен в создании побочных действий так, как это описано в разделе 7.9