Question: Delete occurences of item from non-linear list

Question

Delete occurences of item from non-linear list

Answers 1
Added at 2017-01-02 16:01
Tags
Question

I am trying to delete all occurrences of an element from a list, from any levels of the list. I am required to use a map function though. I am using Common Lisp. For example I'd want to be able to do:

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

What I've tried so far: This function will do what's needed, sort of. It will replace all occurences of the given element with NIL, so it's not exactly what I want.

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

This will do

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

My second try is with the mapcap function, since this one won't return a list the same size as the input list. This will do what's needed, but it will 'destroy' my initial list, as in, it will bring all sublists 'to surface'.

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

So this indeed does (fdelete '(1 2 3 4 (3)) 3) => (1 2 4) but it will also do it wrong if I for example try this:

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

I'd want it to do (fdelete '(1 2 3 (4) (3)) 3)) => (1 2 (4))

I hope my question is well formed and detailed enough, and I am providing working examples. Can someone give me a few hints on how to solve this problem?

Answers to

Delete occurences of item from non-linear list

nr: #1 dodano: 2017-01-02 16:01

Using mapcan is the correct choice since you can wrap in list to get a value or use nil to get item removed. For the list element, if it doesn't already match what to delete, you should check the result of the recursion and wrap it if it's not the empty list.

The solution would look something like:

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

To apply the principle of least surprise I have renamed the function since delete is the destructive version of remove. Also I kept the argument order of the standard functions:

Source Show
◀ Wstecz