Линейно рекурсивная функция разности списков в Common Lisp

Question

Я проходил через это учебник для развлечения, и застрял на самом последнем, что он говорит: "Упражнение:Дайте линейно рекурсивную реализацию объединения и различия ". (для списка)

Профсоюз, не парься.

Разница, пот.

Попытка выглядит примерно так...

(defun list-diff (L1 L2)
  (cond
    ((null L1) L2) 
    ((null (member (first L1) L2)) (cons (first L1) (list-diff (rest L1) L2)))
    (t (list-diff (rest L1) L2))
  )
)

Теперь это возвращает все элементы, находящиеся в L1, которых нет в L2, но это просто возвращает все L2 (очевидно).Аналогично, если я изменю L2 в строке 3 на "nil", то он просто вернет все L1, которых нет в L2, но ни одного из L2.

Мои попытки обходных путей не выглядят рекурсивными, и когда они таковыми являются, я в конечном итоге получаю переполнение стека (например, если я пытаюсь вызвать (list-diff L2 L1) где-нибудь).

Любое из его других упражнений, таких как пересечение списков, требует только выполнения элементов L1.Здесь я хочу вычеркнуть ключевые элементы из L2 или выполнить (list-diff L2 L1), а затем объединить результаты из обоих, но это уже не совсем линейно-рекурсивно.

Мысли?

(на самом деле, это не домашнее задание.Я просто подумал, что попробую посмотреть на какой-нибудь шепелявый для развлечения.)

Редактировать:функция, которая делает это должным образом, основываясь на ответах, является:

(defun list-diff (L1 L2)
  (cond
    ((null L1) nil)
    ((null (member (first L1) L2)) (cons (first L1) (list-diff (rest L1) L2)))
    (t (list-diff (rest L1) L2))
  )
)

Answer 1

В установленная разница операция L1 \ L2 определяется как все элементы e, такие, что e находится в L1, но e не в L2.Так что мне кажется, что ваша вторая попытка действительно верна:

Аналогично, если я изменю L2 в строке 3 на "nil", то он просто вернет все из L1, которых нет в L2, но ничего из L2.

Похоже, что вы пытаетесь вычислить симметричная разница, хотя мне не ясно, что это то, чего требует упражнение.

Если вы хотите быть умнее в этом вопросе, вы, вероятно, можете передать третий список в функцию, которая будет служить аккумулятором.Когда в L1 есть элементы, вставьте первый элемент в накопитель (и вызывайте рекурсивно), когда (null (member (first L1) L2)).Когда значение L1 равно нулю, проверьте элементы L2 по списку накопителей, проделав то же самое.Когда значения L1 и L2 равны нулю, верните список накопителей.

Answer 2

В Lisp это определение "заданной разницы":

set-difference list1 list2 &key (test #'eql) test-not (key #'identity)
   Function
   Returns a list of elements of list1 that do not appear in list2. 

Это ваша измененная реализация:

(defun list-diff (L1 L2)
  (cond
    ((null L1) L1)
    ((member (first L1) L2) (list-diff (rest L1) L2))
    (t (cons (first l1) (list-diff (rest l1) l2)))))