2.40.6.9 Deletion

Function: ilist idelete x ilist

Function: ilist idelete x ilist =

idelete uses the comparison procedure =, which defaults to equal?, to find all elements of ilist that are equal to x, and deletes them from ilist. The dynamic order in which the various applications of = are made is not specified.

The ilist is not disordered: elements that appear in the result ilist occur in the same order as they occur in the argument ilist. The result may share a common tail with the argument ilist.

Note that fully general element deletion can be performed with the iremove procedures, e.g.:

;; idelete all the even elements from LIS:
(iremove even? lis)

The comparison procedure is used in this way: ‘(= x ei)’. That is, x is always the first argument, and an ilist element is always the second argument. The comparison procedure will be used to compare each element of ilist exactly once; the order in which it is applied to the various ei is not specified. Thus, one can reliably remove all the numbers greater than five from an ilist with ‘(idelete 5 ilist <)’.

Function: ilist idelete-duplicates ilist

Function: ilist idelete-duplicates ilist =

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(n2) for n–element ilists. Uniquifying long ilists can be accomplished in O(n log 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))