Как вы гарантируете, что список ассоциаций поддерживает уникальные ключи в Emacs?

Question

Учитывая частоту добавления ключей в списки ассоциаций, такие как auto-mode-alistЯ предполагаю, что есть какой-то идиоматический метод для поддержки списков ассоциаций с уникальными ключами, но ему еще не приходилось сталкиваться с этим.

Допустим, я выполняю следующее:

(setq alist '())
(add-to-list 'alist '(a . 1))
(add-to-list 'alist '(a . 2))
(add-to-list 'alist '(b . 3))

После запуска этого alist содержит ((b . 3) (a . 2) (a . 1)), я вижу это add-to-list может принять необязательный compare-fnтак что я предполагаю, что есть какой-то метод, который я мог бы пройти, чтобы получить ((b . 3) (a . 1)) в результате. Я также знаю, что мог бы использовать для этого хеш-таблицы, но мне было любопытно, как это сделать идиоматически со списком ассоциаций.

Answer 1

Как показывает ваш пример, не требуется, чтобы списки ассоциаций имели уникальные ключи, и нет особой причины ожидать, что у них будут уникальные ключи - по сути, это просто список списков без ограничений на carс вложенных списков.

Я считаю, что идиоматично использовать тот факт, что нет никаких ограничений на ключи для переопределения исходных пар ключ / значение, выдвигая новую пару в начало списка. Некоторые из основных функций для списков неявно работают в этом направлении. Вот, например, строка документации для assoc:

Return non-nil if KEY is `equal' to the car of an element of LIST.
The value is actually the first element of LIST whose car equals KEY.

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

Обновить. Если вы действительно хотите предотвратить add-to-list от затенения предыдущей пары ключ / значение (хотя вы как бы боретесь с языком при этом), вы можете определить следующую функцию и передать ее compare-fn параметр в add-to-list (обратите внимание, что он не проверяет ошибки):

(defun key-used-p (elt1 elt2)
  "Helper function for add-to-list: returns non-nil if key is
already in use in an association list."
  (eq (car elt1) (car elt2)))

(setq alist '((a . 1) (b . 1) (c . 1)))        ; original list
(add-to-list 'alist '(a . 2) nil #'key-used-p) ; adds nothing because a in use
(add-to-list 'alist '(d . 2) nil #'key-used-p) ; adds (d . 2)

Answer 2

Не беспокойтесь о списках с дублирующимися ключами. Обычно, когда вы используете списки, вы получаете доступ к элементам с assoc, который возвращает первый соответствующий элемент в списке и игнорирует остальные. Таким образом, идиоматический способ обработки списков заключается в том, что каждый раз, когда вы хотите заменить элемент в списке alist новым значением для старого ключа, вы просто добавляете новую пару с точками и игнорируете старую. Поэтому независимо от того, сколько у вас дубликатов, assoc буду игнорировать их. Вы работаете через Alist API и игнорируете детали реализации, так сказать. Структура Алиста как списка низкоуровневая и неактуальная.

Многие полезные функции Common Lisp реализованы через библиотеку CL с префиксом cl-, Одна такая функция cl-remove-duplicates, что очень универсально благодаря ключевым аргументам. (Если вы хотите решение Common Lisp, просто используйте remove-duplicates). Поэтому, если по какой-то причине вам нужен список с уникальными ключами, удалите все дублирующиеся элементы, но только что добавленные:

(cl-remove-duplicates my-list
                      :key #'car
                      :from-end t)

обеспечение car так как ключ эквивалентен написанию пользовательской тестовой функции, которая сравнивает только автомобили из каждых 2 элементов: :test (lambda (a b) (equal (car a) (car b)), Почему это работает? cl-remove-duplicates уже использует eql в качестве своей тестовой функции и, как сказано в руководстве, ключевая функция похожа на фильтр, через который элементы воспринимаются функцией, поэтому она не сравнивает сами элементы, а сначала помещает элементы через ключевую функцию.

Вы должны использовать библиотеку CL каждый раз, когда она кажется удобной и элегантной, потому что она поставляется с Emacs, но давайте предположим, что вы не можете использовать ее по какой-то причине. Тогда есть dash.el сторонняя библиотека для манипулирования списками. Имеет функцию -distinct, который удаляет несколько вхождений в списке. Но он работает с элементами списка дословно, он не понимает списки! Или это? Вы можете предоставить пользовательскую функцию сравнения, назначив ее -compare-fn переменная и -distinct будет использовать его вместо того, чтобы прямо сравнивать его с equal, Просто временно предоставьте функцию, которая сравнивает по клавишам let:

(let ((-compare-fn (lambda (a b)
                     (equal (car a) (car b)))))
  (-distinct my-list))