chickadee » srfi-116 » idelete-duplicates

idelete-duplicates removes duplicate elements from the ilist argument. If there are multiple equal elements in the argument ilist, the result ilist 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 ilist -- idelete-duplicates does not disorder the ilist (hence it is useful for "cleaning up" immutable association lists).

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

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

Be aware that, in general, idelete-duplicates runs in time O(n^2) for n-element ilists. Uniquifying long ilists can be accomplished in O(n lg n) time by sorting the ilist 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.

(idelete-duplicates (iq a b a c a b c z)) ;=> (a b c z)

;; Clean up an ialist:
(idelete-duplicates (iq (a . 3) (b . 7) (a . 9) (c . 1))
                   (lambda (x y) (eq? (icar x) (icar y))))
    ;=> ((a . 3) (b . 7) (c . 1))