Replace element of alist using `equal` even if key does not exist

Question

I have an alist whose keys are strings, and I need to set the value for one of its keys. If the key is not present, I need to add it. So for example,

(alist-set "a" "bb" '(("a" . "b") ("c" . "d"))) => '(("a" . "bb") ("c" . "d"))
(alist-set "a" "bb" '(("c" . "d"))) => '(("a" . "bb") ("c" . "d"))

Introducing duplicate entries is not acceptable. Mutating the original alist is allowed.

Here are some incorrect solutions:

• Using alist-get:

   (setf (alist-get key alist) val)
  

  This is incorrect because alist-get compares keys using eq, but string keys must be compared using equal. I could implement a new version of the setf accessor for alist-get that uses equal, but the original implementation in gv.el is 26 lines of code. That is a lot of boilerplate for this simple operation.

• Using setcdr with assoc:

  (setcdr (assoc key alist) val)
  (setf (cdr (assoc key alist)) val)
  

  This is incorrect because it fails when the key is not present in the alist to begin with.

• Use the fact that earlier entries in an alist shadow later ones:

  (push (cons key val) alist)
  

  This is incorrect because it introduces a duplicate entry for key in the alist.

Here are some questions whose answers do not answer this question:

• Looking for a simple way to update an alist without introducing degeneracies
• How to replace an element of an alist?

Answer 1

Since Emacs version 26.1, alist-get accepts an optional argument testfn; when this argument is non-nil, then alist-get uses it to compare the keys instead of eq.

Then you can do:

(let ((alist (list (cons "a" "b") (cons "c" "d"))))
  (setf (alist-get "a" alist nil nil 'equal) "bb")
  alist)
=> (("a" . "bb") ("c" . "d"))

Another way is to use the builtin library map.el. This library adds an abstration layer to handle uniformly hash-tables, alists and arrays. This has the advantage that if you later decide to use a hash-table instead of an alist, your code using map.el remains valid.

With map.el you'd write:

(require 'map)
(let ((map (list (cons "a" "b") (cons "c" "d"))))
  (map-put map "a" "bb" 'equal)
  map)
=> (("a" . "bb") ("c" . "d"))

Answer 2

I came up with this solution, which does not require traversing the alist twice, and satisfies all of my other conditions.

(defun alist-set (key val alist &optional symbol)
  "Set property KEY to VAL in ALIST. Return new alist.
This creates the association if it is missing, and otherwise sets
the cdr of the first matching association in the list. It does
not create duplicate associations. By default, key comparison is
done with `equal'. However, if SYMBOL is non-nil, then `eq' is
used instead.

This method may mutate the original alist, but you still need to
use the return value of this method instead of the original
alist, to ensure correct results."
  (if-let ((pair (if symbol (assq key alist) (assoc key alist))))
      (setcdr pair val)
    (push (cons key val) alist))
  alist)

You will need to include

(require 'subr-x)

in order to have access to if-let.