Scheme removing nested duplicates

问题:

So I'm programming in scheme and made a function that removes duplicated but it doesn't work for nested. I can't really figure out a good way to do this, is there a way to modify the current code I have and simply make it work with nested? lists?

Here's my code

(define (duplicates L)
  (cond ((null? L)
         '())
        ((member (car L) (cdr L))
         (duplicates (cdr L)))
        (else
         (cons (car L) (duplicates (cdr L))))))

回答1:

So your procedure jumps over elements that exist in the rest of the list so that (duplicates '(b a b)) becomes (a b) and not (b a). It works for a flat list but in a tree you might not have a first element in that list but a list. It's much easier to keep the first occurrence and blacklist future elements. The following code uses a hash since you have tagged racket. Doing this without a hash requires multiple-value returns or mutation.

(define (remove-duplicates lst)
  (define seen (make-hasheqv))
  (define (ins val)
    (hash-set! seen val #t)
    val)
  (let aux ((lst lst))
    (cond ((null? lst) lst)
          ((not (pair? lst)) (if (hash-has-key? seen lst) '() (ins lst)))
          ((pair? (car lst)) (let ((a (aux (car lst))))
                               (if (null? a) ; if the only element is elmininated
                                   (aux (cdr lst))
                                   (cons a (aux (cdr lst))))))
          ((hash-has-key? seen (car lst)) (aux (cdr lst)))
          (else (cons (ins (car lst)) ; NB! order of evaluation in Racket is left to right but not in Scheme! 
                      (aux (cdr lst)))))))

;; test
(remove-duplicates '(a b a))                 ; ==> (a b)
(remove-duplicates '(a (a) b a))             ; ==> (a b)
(remove-duplicates '(a (b a) b a))           ; ==> (a (b))
(remove-duplicates '(a b (a b) b a))         ; ==> (a b)
(remove-duplicates '(a (a . b) b a))         ; ==> (a b)
(remove-duplicates '(a b (a b . c) b a . d)) ; ==> (a b c . d)