chickadee » srfi-1 » delete-duplicates

delete-duplicates removes duplicate elements from the list argument. If there are multiple equal elements in the argument list, the result list only contains the first or leftmost of these elements in the result. The order of these surviving elements is the same as in the original list -- delete-duplicates does not disorder the list (hence it is useful for "cleaning up" association lists).

The = parameter is used to compare the elements of the list; it defaults to equal?. If X comes before Y in LIST, then the comparison is performed (= X Y). The comparison procedure will be used to compare each pair of elements in LIST no more than once; the order in which it is applied to the various pairs is not specified.

Implementations of delete-duplicates are allowed to share common tails between argument and result lists -- for example, if the list argument contains only unique elements, it may simply return exactly this list.

Be aware that, in general, delete-duplicates runs in time O(n^2) for N-element lists. Uniquifying long lists can be accomplished in O(n lg n) time by sorting the list to bring equal elements together, then using a linear-time algorithm to remove equal elements. Alternatively, one can use algorithms based on element-marking, with linear-time results.

delete-duplicates! is the linear-update variant of delete-duplicates; it is allowed, but not required, to alter the cons cells in its argument list to construct the result.

(delete-duplicates '(a b a c a b c z)) => (a b c z)
 
;; Clean up an alist:
(delete-duplicates '((a . 3) (b . 7) (a . 9) (c . 1))
                   (lambda (x y) (eq? (car x) (car y))))
    => ((a . 3) (b . 7) (c . 1))