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

Question

下面的过程将两个列表和 returns 它们的并集作为有序列表。

(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)

这是因为，在这种情况下，第一个分支为真，函数 returns nil.

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

Function that returns the union(in alphabetic order) of two sets in Lisp

recursion

common-lisp

ordered-set