Ассоциативные списки (alist) и списки свойств (plist)

Ассоциативные списки (alist) и списки свойств (plist): простейшие «словари» Lisp, их идиомы, плюсы, ограничения и когда переходить на хеш-таблицы.

Ассоциативный список (alist) — это список пар «ключ . значение», по которому ищут линейно; plist — плоский список вида ключ, значение, ключ, значение... Оба дают «словарь без таблицы».

Зачем это: словарь из обычного списка

Прежде чем тянуться за хеш-таблицей, Lisp-программист часто обходится списком. Причина — списки в Lisp дёшевы, литеральны (легко записать руками), неизменяемы по духу и прекрасно подходят для маленьких отображений «ключ → значение»: конфигурации, параметры, временные ассоциации. Два канонических способа — alist и plist. Они медленнее хеш-таблиц (поиск линейный), но проще, не требуют создания объекта, легко строятся и разбираются, дружат с функциональным стилем. Понимать их обязательно: они пронизывают код Lisp, включая сам стандарт (результаты многих функций — alist/plist).

Есть и менее очевидное достоинство, которое делает alist/plist незаменимыми даже при наличии хеш-таблиц: они литеральны и прозрачны. Alist можно написать прямо в исходнике как константу, увидеть целиком при печати, сравнить через equal, сериализовать print'ом и прочитать обратно read'ом без всякого кода. Хеш-таблица так не умеет: у неё нет читаемого литерального представления, печать показывает лишь #<HASH-TABLE ...>, и восстановить её из текста напрямую нельзя. Поэтому для конфигов, тестовых данных, обмена структурами «как данные» alist часто удобнее хеш-таблицы, а не просто «проще для маленького». Это снова про гомоиконность: alist — это и структура данных, и читаемый текст одновременно, что бесценно для отладки и сериализации.

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

Alist — список, каждый элемент которого — пара (cons) (ключ . значение). Поиск по ключу — функцией assoc: она идёт по списку и возвращает первую пару с совпавшим ключом (или nil). Значение достают через cdr найденной пары.

(defparameter *capitals*
  '((:france  . "Париж")
    (:germany . "Берлин")
    (:japan   . "Токио")))

(assoc :germany *capitals*)         ; => (:GERMANY . "Берлин")
(cdr (assoc :germany *capitals*))   ; => "Берлин"
(assoc :mars *capitals*)            ; => NIL  (нет такого ключа)

;; обратный поиск — по значению — через rassoc:
(car (rassoc "Токио" *capitals* :test #'string=))  ; => :JAPAN

Важная идиома: чтобы «обновить» значение в alist, не меняют существующую пару, а добавляют новую в начало — assoc найдёт её первой, «затенив» старую. Это в духе функционального программирования: старый alist не портится, можно держать историю версий. По умолчанию assoc сравнивает ключи через eql — отлично для символов, ключевых слов, чисел. Для строковых ключей передавайте :test #'string=, иначе совпадения не будет.

;; «обновление» добавлением в начало (старое затеняется)
(defparameter *config* '((:debug . nil) (:level . 1)))
(push '(:debug . t) *config*)       ; теперь (:DEBUG . T) впереди
(cdr (assoc :debug *config*))       ; => T  (новое значение)

;; функциональное обновление без разрушения:
(defun aset (key val alist)
  (cons (cons key val) alist))      ; вернуть НОВЫЙ alist

Списки свойств (plist)

Plist — «плоская» альтернатива: один список, где элементы чередуются ключ, значение, ключ, значение. Поиск — функцией getf, которая идёт по списку с шагом два и возвращает значение за совпавшим ключом. Ключи в plist почти всегда — ключевые слова.

(defparameter *person*
  '(:name "Анна" :age 30 :city "Казань"))

(getf *person* :age)          ; => 30
(getf *person* :city)         ; => "Казань"
(getf *person* :phone)        ; => NIL  (нет ключа)
(getf *person* :phone "—")    ; => "—"  (значение по умолчанию)

Plist особенно удобен как «именованные аргументы налету» и тесно связан с &key-параметрами функций: список (:color :red :width 3) — это и plist, и набор именованных аргументов. Изменять plist можно деструктивно через (setf (getf place key) value) — но чаще их строят заново. getf сравнивает ключи через eq (поэтому ключевые слова идеальны).

Глубокая связь plist с механизмом &key стоит того, чтобы её подчеркнуть, — это объясняет, почему ключевые слова в Lisp так распространены. Когда вы вызываете (make-pen :color :red :width 3), аргументы после имени функции — это буквально plist, который функция разбирает по своим &key-параметрам. То есть «именованные аргументы» в Common Lisp — не отдельная синтаксическая фича, а прямое применение plist-структуры. Более того, функция может принять «остаток» именованных аргументов как plist через &rest и передать его дальше или хранить — поэтому plist'ы естественно «протекают» через слои кода как наборы опций. Эта унификация «структура данных = протокол вызова» очень в духе Lisp: вместо отдельных сущностей для «словаря опций» и «именованных параметров» — одна структура, работающая в обеих ролях. Поняв это, вы перестаёте видеть в keyword-аргументах что-то особое: это просто plist, который функция читает getf'ом.

alist против plist: что выбрать

Эмпирика: если ключи — строки или нужен обратный поиск/тонкая настройка сравнения — alist; если ключи — ключевые слова и данные похожи на «набор опций» — plist. Для свойств самих символов есть встроенный механизм (get symbol key) — это plist, прикреплённый к символу.

Этот «список свойств символа» (его так и называют — property list, отсюда и слово plist) заслуживает упоминания как историческая и практическая деталь. У каждого символа есть собственная ячейка plist, доступная через (get symbol key) и устанавливаемая через (setf (get symbol key) value). Исторически это был один из старейших способов хранить данные в Lisp — «повесить» атрибуты прямо на имя: (setf (get 'iron 'density) 7.87). Сегодня для этого чаще берут хеш-таблицы или слоты объектов, но механизм жив и иногда удобен для глобальных метаданных, привязанных к символам (например, в реализации макросов и DSL, где нужно пометить символ дополнительной информацией). Знать о нём стоит хотя бы потому, что вы встретите его в старом коде и в некоторых библиотеках, и потому что он наглядно показывает, насколько символ — богатый объект: у него есть не только имя и значение, но и собственное хранилище произвольных свойств.

Граница применимости: когда хеш-таблица

И alist, и plist ищут линейно: время поиска O(n). На десятке-двух элементов это незаметно и даже быстрее хеш-таблицы (нет накладных на хеширование, лучше локальность памяти). Но когда отображение большое (сотни-тысячи ключей) или поиск идёт в горячем цикле, линейность убивает производительность — пора на хеш-таблицу (следующие уроки), дающую амортизированный O(1). Правило: маленькое и редко — список; большое или часто — хеш-таблица. Не оптимизируйте преждевременно: для конфигов и небольших ассоциаций alist/plist читабельнее и проще.

Стоит развеять интуицию «хеш-таблица всегда быстрее» — она неверна для малых размеров. У хеширования есть постоянные накладные расходы: вычислить хеш-код ключа, найти корзину, иногда разрешить коллизию. На трёх-пяти элементах эти накладные перевешивают, и простой линейный проход по списку из нескольких cons-ячеек, лежащих рядом в памяти, оказывается быстрее — ещё и за счёт лучшей локальности кеша процессора. Точка перелома зависит от реализации и типа ключей, но грубо лежит в районе десятков элементов. Поэтому совет «бери хеш-таблицу для словарей» хорош как умолчание для крупных данных, но для крошечных отображений alist не только проще, но и эффективнее. Зрелое решение учитывает ожидаемый размер: знаете, что ключей всегда единицы, — alist; могут быть сотни и тысячи — хеш-таблица. Это пример того, как «асимптотически медленнее» не означает «медленнее на практике» для конкретного масштаба.

Контраст со Scheme

В Scheme alist'ы устроены так же (пары (k . v)), но функция поиска называется assq/assv/assoc в зависимости от предиката сравнения: assq использует eq?, assv — eqv?, assoc — equal? (или заданный предикат в R7RS). Это явное разделение по предикату — характерно для Scheme, где функции называют по используемому сравнению. Plist в Scheme штатно не выделен как идиома (нет getf), но никто не мешает хранить плоский список и ходить по нему; на практике в Scheme для словарей чаще берут hash-table из библиотек. Общая идея «словарь из списка пар» полностью совпадает.

;; Scheme: alist и поиск с разными предикатами
(define caps '((france . "Париж") (germany . "Берлин")))
(assq 'germany caps)      ; => (germany . "Берлин")  ; eq?-сравнение
(cdr (assq 'germany caps)) ; => "Берлин"

Как работает под капотом

Оба представления — обычные связные списки из cons-ячеек, никакой особой структуры. assoc — простой цикл: пройти по списку, на каждом элементе сравнить его car (ключ) с искомым выбранным предикатом; вернуть элемент при совпадении. getf — цикл с шагом два: сравнить текущий элемент с ключом, при совпадении вернуть следующий. Отсюда и линейная стоимость, и преимущество на коротких списках (один проход по смежной памяти cons-ячеек). «Обновление через push в начало» работает потому, что assoc/getf находят первое совпадение — добавленный в голову ключ перекрывает старый, а старый остаётся в хвосте нетронутым (это и даёт неразрушающую семантику и дешёвый «откат» через сохранённый старый список).

Частые ошибки

• Забыть cdr после assoc. assoc возвращает пару, а не значение. Значение — это (cdr (assoc key alist)).
• Строковые ключи без :test. По умолчанию assoc сравнивает через eql — строки так не совпадут. Передавайте :test #'string=.
• Путать assoc и getf. assoc — для alist (пары), getf — для plist (плоский список). Применить не к той структуре — ошибка или мусор.
• Линейный поиск в горячем цикле. На больших данных alist/plist деградируют до O(n) на поиск. Переходите на хеш-таблицу.
• Деструктивно менять общий alist. Если на список ссылаются другие места, setf/rplacd его испортит. Предпочитайте функциональное обновление (push новой пары / новый список).

Итоги

• alist — список пар (ключ . значение); поиск assoc (значение в cdr), обратный — rassoc.
• plist — плоский ключ значение ключ значение; поиск getf (можно со значением по умолчанию).
• «Обновление» — добавление в начало: assoc/getf находят первое совпадение, затеняя старое (неразрушающе).
• Строковые ключи в alist требуют :test #'string=; plist обычно на ключевых словах (сравнение eq).
• Поиск линейный (O(n)): отлично для маленьких отображений, плохо для больших — тогда хеш-таблица.
• В Scheme alist тот же; функции поиска (assq/assv/assoc) различаются предикатом сравнения.