在通用Lisp中，我可以使用map函数实现将两个列表合并为一个列表吗？

Question

有两份清单如下：

(setf l1 '((1 . 1) (2 . 2) (3 . 3)  (4 . 4) (5 . 5)))
(setf l2 '(2  22  4  44  6 66))    ;; this is a alist

我想把这两份清单合并为一份，例如：

((1 . 1) (2 . 22) (3 . 3)  (4 . 44) (5 . 5)  (6 . 66))

我可以使用一些Set函数，比如intersection和set-difference。

但是我想用没有迭代器函数的map函数来实现，比如do，loop，我不知道怎么做。

Answer 1

对于列表，这看起来不是合并，而是更新:您希望用l1中指定的l2更新更新数据。

(defun update (target updates)
  "Returns a copy of the alist TARGET where the values are updated according
to the plist UPDATES."
  (mapcar (lambda (assoc)
            (let ((update (getf updates (car assoc) :not-found)))
              (if (eq update :not-found)
                  assoc
                  (cons (car assoc) update))))
          target))

如果updates大于几十个元素，那么首先应该将其转换为相对于随机查找具有更好伸缩性的数据结构。

Answer 2

首先，您需要将l2转换为真诚的主义者：

(setq l3 (loop for (a b) on l2 by #'cddr collect (cons a b)))
==> ((2 . 22) (4 . 44) (6 . 66))

接下来，您可以对它们进行合并：

(setq l4 (merge 'list l1 l3 #'< :key #'car))
==> ((1 . 1) (2 . 2) (2 . 22) (3 . 3) (4 . 4) (4 . 44) (5 . 5) (6 . 66))

现在你可以移除复本了(小心！)不必要的二次复杂度！)：

(setq l5 (delete-duplicates l4 :key #'car))
==> ((1 . 1) (2 . 22) (3 . 3) (4 . 44) (5 . 5) (6 . 66))

1. 我不认为你能用一张简单的地图就能做到这一点。
2. 最有效的实现将使用单个手工构建的循环，而不是系统功能。