在Lisp中返回两个集合的并集（按字母顺序）的函数

Question

以下过程获取两个列表，并将它们的并集作为有序列表返回。

(defun stable-union (lst1 lst2)
  (cond ((null lst1) lst2)
        ((null lst2) lst1)
        ((and (null lst1) (null lst2)) nil)
        (t
         (let ((el1 (car lst1))
               (el2 (car lst2)))
           (cond ((string= el1 el2)
                  (cons el1
                     (stable-union (cdr lst1)  (cdr lst2))))
                  ((string< el1 el2)
                   (cons el1
                         (stable-union (cdr lst1)  lst2)))
                  (t
                   (cons el2
                         (stable-union lst1 (cdr lst2)))))))))

它仅适用于某些示例，而不适用于其他示例。例如：

STABLE-UNION: (STABLE-UNION '(A B C) '(B A D)) failed: 
Expected (A B C D) but saw (A B A C D)
STABLE-UNION: (STABLE-UNION '(A B C) '(A D B E)) failed: 
Expected (A B C D E) but saw (A B C D B E)
STABLE-UNION: (STABLE-UNION '(C B A) '(A E B D)) failed: 
Expected (C B A E D) but saw (A C B A E B D)

您能指导我在代码中出错的地方吗？非常感谢。

Answer 1

上面的函数仅适用于由按字典顺序排序的符号组成的列表。因此，例如，它适用于'(A B C) '(A B D)，但不适用于'(A B C) '(B A D)。

有几种纠正方法。最简单的方法是通过对两个参数进行排序（使用稳定排序）来调用它，例如：

(defun stable-union-general (lst1 lst2)
   (stable-union (stable-sort lst1 #'string<) (stable-sort lst2 #'string<)))

(stable-union-general '(A B C) '(B A D))
(A B C D)

另一种效率较低的方法是通过考虑无序列表来更改算法。

最后要注意的是，外部条件的第三分支从未被规定： ((and (null lst1) (null lst2)) nil)

这是因为在这种情况下，第一个分支为true，并且该函数返回nil。