Удалить вхождения элемента из нелинейного списка

Question

Я пытаюсь удалить все вхождения элемента из списка из любых уровней списка. Я должен использовать функцию карты, хотя. Я использую Common Lisp. Например, я хотел бы быть в состоянии сделать:

(fdelete '(1 2 3 4 (3)) 3) => (1 2 4) 

То, что я пытался до сих пор: Эта функция будет делать то, что нужно, вроде. Он заменит все вхождения данного элемента на NIL, так что это не совсем то, что я хочу.

(defun fdelete (l e) 
    (cond 
     ((null l) 0) 
     ((equal l e) nil) 
     ((atom l) l) 
     (t (mapcar (lambda(l) (fdelete l e)) l)) 
    ) 
) 

Это сделает

(fdelete '(1 2 3 4 (3)) 3) => (1 2 NIL 4 (NIL)) 

Моя вторая попытка это с функцией mapcap, так как это не будет возвращать список один и тот же размер, что и входной список. Это сделает все, что нужно, но оно «уничтожит» мой первоначальный список, так как в нем будут отображаться все субблисты на поверхность ».

(defun fdelete (l e) 
    (cond 
     ((null l) 0) 
     ((equal l e) nil) 
     ((atom l) (list l)) 
     (t(mapcan(lambda(x) (fdelete x e))l)) 
    ) 
) 

Так что это действительно делает (fdelete '(1 2 3 4 (3)) 3) => (1 2 4) , но он также будет делать это неправильно, если я, например, попробуйте следующее:

(fdelete '(1 2 3 (4) (3)) 3)) => (1 2 4) 

Я хочу, чтобы это сделать (fdelete '(1 2 3 (4) (3)) 3)) => (1 2 (4))

Я надеюсь, что мой вопрос хорошо сформирован и достаточно подробен, и я предоставляю рабочие примеры. Может ли кто-нибудь дать мне несколько советов о том, как решить эту проблему?

Answer 1

Использование mapcan является правильным выбором, так как вы можете обернуть в list, чтобы получить значение или использовать nil, чтобы получить элемент удален. Для элемента списка, если он еще не соответствует тому, что нужно удалить, вы должны проверить результат рекурсии и обернуть его, если это не пустой список.

решение будет выглядеть примерно так:

(defun remove-deep (item list) 
    (mapcan (lambda (cur) 
      (cond ((equal item cur) '()) 
        ...)) 
      list)) 

(remove-deep 3 '(1 nil 2 3 (3) (3 4))) 
; ==> (1 nil 2 (4)) 

Чтобы применить principle of least surprise я переименовал функцию, так как delete является деструктивной версией remove. Также я сохранил порядок аргументов standard functions: