How do you ensure an association list maintains unique keys in Emacs

Question

Given the frequency that keys are added to association lists like auto-mode-alist, I presume there is some idiomatic method for maintaining association lists with unique keys, but have yet to encounter it.

Let's say I execute the following:

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

After running that, alist contains ((b . 3) (a . 2) (a . 1)). I see that add-to-list can take an optional compare-fn, so I presume there is some method I could pass to get ((b . 3) (a . 1)) as the result. I'm also aware I could use hash tables for this, but was curious how to do it idiomatically with an association list.

Guinea

Answer 1

There's no requirement that association lists have unique keys, as your example shows, nor is there any particular reason to expect them to have unique keys -- at base, it's just a list of lists with no restrictions on the cars of the nested lists.

I believe it's idiomatic to exploit the fact that there are no restrictions on the keys to override initial key/value pairs by pushing a new pair onto the front of the list. Some of the core functionality for alists works implicitly along these lines. Here, for example, is the docstring for 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.

Hence, it returns only the first element, regardless of how many other elements come later in the list with the same key. That can be a pretty useful feature.

Update. If you really want to prevent add-to-list from shadowing a prior key/value pair (although you're kind of fighting the language in doing so), you can define the following function and pass it to the compare-fn parameter in add-to-list (note that it does zero error-checking):

(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)

Contemporize

Another way to put this is that this is one of the advantages of an alist (likewise, for a plist): older entries are shadowed by newer ones. IOW, the quick answer to the question is Don't bother (or Why bother?). – Hegarty

Answer 2

Don't worry about alists having items with duplicate keys. Usually when you use alists, you access items with assoc, which returns the first matching item in a list and ignores the rest. So the idiomatic way to treat alists is that every time you want to replace an item in alist with a new value for an old key, you just add a new dotted pair and ignore the old one. So no matter how many duplicates you have, assoc will ignore them. You work via alist API and ignore the implementation details, so to speak. Alist's structure as a list is low-level and irrelevant.

Many useful Common Lisp functions are implemented through CL library, prefixed with cl-. One such function is cl-remove-duplicates, which is very versatile due to keyword arguments. (If you want a Common Lisp solution, just use remove-duplicates). So if for some reason you want an alist with unique keys, remove all duplicate items but the newly added:

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

Providing car as a key is equivalent to writing a custom test function that compares only cars of every 2 elements: :test (lambda (a b) (equal (car a) (car b)). Why does it work? cl-remove-duplicates already uses eql as its test function and, as it says in the manual, a key function is like a filter through which the elements are seen by the function, so it doesn't compare the elements themselves, but first put elements through the key function.

You should use CL library every time it seems handy and elegant, because it's shipped with Emacs, but let's assume that you can't use it for some reason. Then there is dash.el third-party list manipulation library. It has a function -distinct, that removes multiple occurrences in a list. But it works with elements of a list verbatim, it doesn't understand alists! Or does it? You could supply a custom comparison function by assigning it to a -compare-fn variable, and -distinct will use it instead of bluntly comparing it with equal. Just temporarily provide a function that compares by keys with let:

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

Feedback