如何确保关联列表在 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没有限制。

我相信利用键

没有限制的事实，通过将新键/值对推到列表的前面来覆盖初始键/值对是惯用的。 alists的一些核心功能隐式地沿着这些思路工作。 例如，这里是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隐藏先前的键/值对(尽管你这样做有点与语言作斗争(，你可以定义以下函数并将其传递给 add-to-list 中的 compare-fn 参数(请注意，它执行零错误检查(：

(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

不要担心 alist 有重复键的项目。通常，当您使用 alist 时，您可以使用 assoc 访问项目，这将返回列表中的第一个匹配项目并忽略其余项目。因此，处理 alist 的惯用方法是，每次您想用旧键的新值替换 alist 中的项目时，您只需添加一个新的虚线对并忽略旧值。因此，无论您有多少重复项，assoc都会忽略它们。可以这么说，您通过 alist API 工作并忽略实现细节。Alist作为列表的结构是低级的，无关紧要。

许多有用的 Common Lisp 函数都是通过 CL 库实现的，前缀为 cl- 。一个这样的函数是cl-remove-duplicates，由于关键字参数，它非常通用。(如果你想要一个通用的Lisp解决方案，只需使用remove-duplicates(。因此，如果出于某种原因您想要一个具有唯一键的 alist，请删除所有重复的项目，但新添加的项目除外：

(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，可以删除列表中的多个匹配项。但是它逐字处理列表的元素，它不理解 alists！还是吗？您可以通过将其分配给-compare-fn变量来提供自定义比较函数，-distinct将使用它，而不是直截了当地将其与equal进行比较。只是暂时提供一个按键与let进行比较的功能：

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