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)
        (loop (cdr rest)
              (let ((first (car rest)))
                (if (member first (cdr rest))
                    (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)
                          (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

created July 12, 1995
last revised July 14, 1995

John David Stone (