list - 在 Common Lisp 中合并两个列表

Question

有没有一种有效的方法来合并 Lisp 中的两个列表，以便如果它们有共同的元素，这些元素将只出现在结果列表中一次？

目前，我有以下代码:

(defun divisible-by-5 (num)
  (zerop (mod num 5)))

(defun divisible-by-3 (num)
  (zerop (mod num 3)))

(remove-if-not #'dividable-by-5 '(loop for i from 1 upto 10 collect i))
(remove-if-not #'divisible-by-3 '(loop for i from 1 upto 10 collect i))

我想合并底部表单返回的两个列表，以按上述方式合并到 on 中。

Answer 1

您已经两次收集列表 (1 ... n)，然后创建删除了某些元素的新列表，然后您将合并那些名单。如果你正在寻找高效的，你应该结合生成初始列表并测试和收集的过程:

(flet ((by-5 (n)
         (zerop (mod n 5)))
       (by-3 (n)
         (zerop (mod n 3))))
  (loop for x from 1 to 50
     unless (and (by-3 x)
                 (by-5 x))
     collect x))

但是如果你真的想单独收集列表然后合并他们，你可以用 UNION 做到这一点:

(flet ((by-5 (n)
         (zerop (mod n 5)))
       (by-3 (n)
         (zerop (mod n 3))))
  (let ((fives (loop for x from 1 to 50 unless (by-5 x) collect x))
        (threes (loop for x from 1 to 50 unless (by-5 x) collect x)))
    (union fives threes)))

现在，union 不能保证保持秩序，但在这种情况下，因为你知道你的列表已经排序，你可以将它们合并更有效一点，因为你可以比较元素，并知道在某一点之后，你不会遇到重复的:

(defun merge-unique (l1 l2 predicate)
  "Returns the result of merging L1 and L2, with no duplicates.
L1 and L2 should already be sets (that is, containing no duplicates), 
and should be ordered according to PREDICATE.  The tail of the result
may be shared with with either L1 or L2."
  (labels ((test (x y)
             (funcall predicate x y))
           (%merge (l1 l2 result)
             "Tail recursive merge procedure.  This could be converted
              to an iterative DO-loop without too much touble."
             (cond
               ((endp l1)
                (nreconc result l2))
               ((endp l2)
                (nreconc result l1))
               ((destructuring-bind (x . xs) l1
                  (destructuring-bind (y . ys) l2
                    (cond
                      ((test x y)
                       (%merge xs l2 (list* x result)))
                      ((test y x)
                       (%merge l1 ys (list* y result)))
                      (t
                       (%merge xs ys (list* x result))))))))))
    (%merge l1 l2 '())))

这是一个使用示例:

(merge-unique '(1 3 5 6) '(1 4 5 6) '<)
;;=> (1 3 4 5 6)