удалить с глубокой рекурсией в lisp

Question

Как я могу реализовать функцию удаления с глубокой рекурсией?

Я знаю, как написать удаление в мелкой рекурсии, но трудно изменить это на глубокую рекурсию.

 (myremove '(1 2) '(1 ((1 2) 3) (4 (5 ((1 2) 5))))) -> (1 (3) (4 (5 (5))))

Answer 1

Полагаю, под "глубокой рекурсией" вы имеете в виду рекурсию по дереву вместо рекурсии по списку?

Более низкоуровневый ответ на это состоит в том, чтобы отбросить как машину, так и CDR из клеток cons, а не только CDR. Хотя я предпочел бы использовать функции более высокого порядка, в этом случае рекурсивно вызывать mapcar:

(defun myremove (item tree)
  (if (atom tree)
      tree
      (mapcar (lambda (subtree) (myremove item subtree))
              (remove item tree :test #'equal))))

РЕДАКТИРОВАТЬ: Вот решение низкого уровня:

(defun myremove (item tree)
  (cond ((atom tree)
         tree)
        ((equal item (car tree))
         (myremove item (cdr tree)))
        ('otherwise
         (cons (myremove item (car tree))
               (myremove item (cdr tree))))))