Функция, которая возвращает объединение (в алфавитном порядке) двух множеств в Лиспе

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

Есть несколько способов исправить это. Самый простой способ - вызвать его, отсортировав (с помощью stable-sort) два аргумента, например:

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