Remove duplicates in a multi-level list using Common Lisp

Question

Remove duplicates in a MULTI-LEVEL list (using Common Lisp) without changing list's inner structure. This problem seems to be a hard nut and a big headache for me.

Source list: (1 2 (6 5) 2 3 (5 4)) ==> Result: (1 (6) 2 3 (5 4))

Here's my not-working decision:

LispWokrs:

(defun F (l &optional (lst (remove-duplicates (flatten l))))

(cond
    ((null l) nil)

    ((atom (car l))

        (if (member (car l) lst)
            (cons (car l) (F (cdr l) (remove (car l) lst)))
            (F (cdr l) lst)))

    (t (cons (F (car l) lst) (F (cdr l) lst)))))

I tried to use lst for keeping a clear set (1 2 6 5 3 4) and I've been trying to remove an element from this set each time I add a new element. But what I get is almost the same source sequence (parallel recursion...):

(f '(1 2 (6 5) 2 3 (5 4))) ==> (1 2 (6 5) 3 (5 4))

(f '(А ((B C E) D (B E A)))) ==> (А ((B C E) D (B E A)))

Then I searched over the net, but there was no decision for this problem.

Answer 1

Try this:

(defun multi-level-list-remove-duplicates (tree)
   (let ((seen NIL))
     (labels ((rec (l)
        (cond
          ((null l) NIL)
          ((consp (car l)) (cons (rec (car l))
                                 (rec (cdr l))))
          ((member (car l) seen) (rec (cdr l)))
          (T (push (car l) seen)
             (cons (car l) (rec (cdr l)))))))
       (rec tree))))

This maintains a list of already-seen values in seen and removes these if seen again. The recursive function rec closes over this value and thus all the sub-lists share one seen variable for each call to multi-level-list-remove-duplicates.