If the order in which the values are arranged does not make any difference, there's an obvious brute-force algorithm: Traverse the list from left to right, discarding any value that recurs later in the list and adding to the result any value that does not.
The(define (strip-duplicates ls) (let loop ((rest ls) (so-far '())) (if (null? rest) so-far (loop (cdr rest) (let ((first (car rest))) (if (member first (cdr rest)) so-far (cons first so-far)))))))
member
procedure, though technically not a predicate, will
return a nonfalse value whenever its first operand is an element of the
list that is its second operand. Unfortunately, the running time of this simple algorithm is quadratic, because it compares every list element to every other list element. For long lists, it may be faster to perform an n lg n sort on the list, so that duplicates are known to be adjacent, and then to apply the following faster procedure:
This procedure retains just the first occurrence of each value. The call to(define (strip-duplicates ls) (if (null? ls) '() (let ((first (car ls))) (let loop ((known first) (rest (cdr ls)) (so-far (list first))) (if (null? rest) (reverse so-far) (let ((first-remaining (car rest))) (loop first-remaining (cdr rest) (if (equal? known first-remaining) so-far (cons first-remaining so-far)))))))))
reverse
(line 9) is superfluous if the order of the
elements in the returned list is irrelevant; having it there ensures that
the order created by the sort will be preserved.
This document is available on the World Wide Web as
http://www.math.grin.edu/~stone/events/scheme-workshop/duplicates.html