# Workshop on Scheme

## Removing duplicates from a list

Problem: Given a list of values, possibly containing duplicates, construct
a new list with the same values but without duplication.
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.

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

The `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:

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

This procedure retains just the first occurrence of each value. The call
to `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`

*created July 12, 1995*

*last revised July 14, 1995*

John David Stone
(stone@math.grin.edu)