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

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)

Это потому, что в этом случае первая ветвь истинна, а функция возвращает nil.