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.

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)