Линейно-рекурсивная функция списка различий в Common Lisp - PullRequest
Новая
       10

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

2 голосов
/ 04 марта 2009

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

Союз, без пота.

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

Попытка выглядит следующим образом. , . 

(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 на «ноль», то он просто возвращает все L1, которых нет в L2, но ни один из L2.

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

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

Мысли?

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

РЕДАКТИРОВАТЬ: функция, которая делает это правильно, на основе ответов: 

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

Ответы [ 2 ]

6 голосов
/ 04 марта 2009

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

Точно так же, если я изменю L2 в строке 3 до «ноль», то он просто возвращает все L1, которые не находятся в L2, но ни один из L2.

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

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

4 голосов
/ 04 марта 2009

В Лиспе это определение «разности множеств»: 

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