объединение в общий список, сохраняя порядок элементов в исходных списках

Question

Я пробираюсь через "ANSI Common Lisp" Пола Грэма (1996). Глава 3, упражнения, кв. 2 просит функцию, как указано в заголовке этого поста. Я использую только то, чему научили в книге до этого момента (очевидно, существует конструкция case, которая может очистить if, но я не против этого в настоящее время).

В качестве первой попытки я написал чередование, в котором сохранились дубликаты:

(defun interleave (x y)
  (if (and (null x)      
           (null y))
      nil
      (if (null x)
          (cons (car y)
                (interleave (cdr y) x))
          ; where y is null, but also for any other case:
          (cons (car x)
                (interleave y (cdr x))))))

После этого у меня появилась идея сохранить перенос элементов, которые были замечены, и перейти к вспомогательной функции, как показано ниже. Тем не менее, ниже, очевидно, довольно некрасиво и трудно понять. Я ищу несколько предложений о направлениях, которые я мог бы принять, чтобы достичь элегантности

Советы по подходу и стилю могут быть столь же полезными на данном этапе, как и предоставление канонического решения. Должен ли мой импульс номер один из приведенного ниже кода извлекать другую функцию? (или, может быть, я пошел в неправильном направлении, пытаясь сперва сохранить керри?) Спасибо вам, хакеры!

(defun new-union (x y)
  (new-union-helper x y '()))  ; <- idea, add a carry to store what's been seen.

(defun new-union-helper (x y seen)
  (if (and (null x)
           (null y))
      nil
      (if (null x)
          (if (not (member (car y) seen)) ; if first el of y hasn't yet been seen...
              ; cons it to the ultimate result & recur, while adding it to seen:
              (cons (car y) (new-union-helper (cdr y) x (cons (car y) seen)))
              ; if it has been seen, just continue, (skip the duplicate):
              (new-union-helper (cdr y) x seen))
          (if (not (member (car x) seen))
              (cons (car x) (new-union-helper y (cdr x) (cons (car x) seen)))
              (new-union-helper (cdr x) y seen)))))

Обновление: я попытался заменить вложенные if s на cond, просмотрев cond в указателе книги. Извините заранее, это так некрасиво ... но если кто-нибудь скажет мне, что я здесь делаю не так, я был бы очень признателен. Этот код работает так же, как и выше, но он печатает ноль в качестве последнего члена в результирующем списке (на некоторых входах), пока не уверен почему.

; attempt to use cond instead:
(defun new-union-helper (x y seen)
  (cond ((and (null x) (null y))
         nil)
        ((and (null x) (not (member (car y) seen)))
         (cons (car y) (new-union-helper (cdr y) x (cons (car y) seen))))
        ((null x)
                       (new-union-helper (cdr y) x seen))
        ((not (member (car x) seen))
         (cons (car x) (new-union-helper y (cdr x) (cons (car x) seen))))
        (t
         (new-union-helper (cdr x) y seen))))

Обновление 2: я попытался улучшить отступ. Ниже приведено то, что я хочу сделать из неформальных тестов. Любые дальнейшие советы о том, что я все еще делаю неправильно? (Я понимаю, что, возможно, мне следует отказаться от этого и пойти другим путем, но, поскольку это учебное упражнение, я хотел вылечить как можно больше потенциальных вредных привычек, прежде чем продолжать идти по новому пути).

Как эта ставка на уродство делает ставку? :) Это теперь доступно для чтения опытному лисперу?

; better (standard?) formatting
(defun new-union-helper (x y seen)
  (cond ((and (null x) 
              (null y))
         nil)
        ((and (null x) 
              (member (car y) seen)) ; replacing find with member stops duplicate nils
         (new-union-helper (cdr y) x seen))
        ((null x)
         (cons (car y) 
               (new-union-helper (cdr y) x 
                                 (cons (car y) seen))))
        ((member (car x) seen) 
         (new-union-helper (cdr x) y seen))
        (t
         (cons (car x) 
               (new-union-helper y (cdr x) 
                                 (cons (car x) seen))))))

Answer 1

(defun new-union (list1 list2 &aux (list3 (reverse list1)))
  (loop for e in list2 do (pushnew e list3))
  (reverse list3))

(defun new-union (list1 list2 &aux (list3 (reverse list1)))
  (dolist (e list2 (reverse list3))
    (pushnew e list3)))

Answer 2

Union принимает два списка в качестве аргументов и возвращает новый список с удаленными дубликатами, как вы знаете.Вы хотите сохранить порядок исходных списков, которые появляются.Конкретный вопрос из книги, если я вспоминаю, состоит в том, что если у вас есть списки:

(new-union '(a b c) '(b a d))

Он должен вернуть:

(A B C D)

, чтобы поддерживать правильный порядок.Так что я думаю, вам нужна функция, которая, очевидно, принимает два списка, и что-то вроде аккумулятора, чтобы вы не разрушали исходные списки.Союз является «неразрушающей» функцией.Поскольку мы работаем со списками, вы можете использовать макрос dolist, чтобы мы могли перебирать оба списка.Это привело бы нас к заключению, что приведенная ниже функция может работать, поскольку она будет поддерживать исходную структуру обоих списков, поддерживать порядок обоих списков и удалять дубликаты:

(defun new-union(lst1 lst2)
   (let((accum nil))
     (dolist(x lst1)
       (push x accum))
     (dolist(y lst2)
       (if(not(find y accum))
      (push y accum)))
     (nreverse accum))

Мы можем выдвинуть каждый элементиз первого списка в наш аккумулятор, а затем мы можем перебрать второй список и ТОЛЬКО поместить его в список, если он не является элементом, который уже был передан в аккумулятор.Таким образом, мы избегаем дубликатов, сохраняем структуру обоих исходных списков и поддерживаем правильный порядок, если мы возвращаем наш аккумулятор с функцией reverse.Давайте проверим это в REPL:

CL-USER> (new-union '(a b c) '(b a d))
(A B C D)

Answer 3

Вот рекурсивная реализация. Это можно сделать быстрее с помощью нескольких хаков. Например, хеш-таблица может использоваться для сохранения увиденных элементов. В этом случае find будет заменен поиском по хеш-таблице с постоянным временем.

(defun new-union (lst1 lst2)
  "return xs U ys preserving order in originals"
  (labels ((rec (xs ys acc)
             (let ((x (car xs))
                   (xx (cdr xs))
                   (y (car ys))
                   (yy (cdr ys)))
               (cond ((and (null xs) (null ys))
                      acc)
                     ((null xs)
                      (or (and (find y acc) (rec xx yy acc))
                          (rec xx yy (cons y acc))))
                     ((null ys)
                      (or (and (find x acc) (rec xx yy acc))
                          (rec xx yy (cons x acc))))
                     ((and (find x acc) (find y acc))
                      (rec xx yy acc))
                     ((and (find x acc) (not (find y acc)))
                      (rec xx yy (cons y acc)))
                     ((and (not (find x acc)) (find y acc))
                      (rec xx yy (cons x acc)))
                     (t (rec xx yy (cons y (cons x acc))))))))
    (nreverse (rec lst1 lst2 nil))))