2.2.5.9 Deletion

Function: delete x list [=]

Function: delete! x list [=]

Use the comparison procedure = (which defaults to equal?) to find all elements of list that are equal to x, and delete them from list. The dynamic order in which the various applications of = are made is not specified.

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

Note that fully general element deletion can be performed with the remove and remove! procedures:

;; Delete all the even elements from LIS:
(remove even? lis)

The comparison procedure is used in this way: (= x ei); that is, x is always the first argument, and a list element is always the second argument. The comparison procedure will be used to compare each element of list 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 5 from a list with (delete 5 list <).

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

Function: delete-duplicates list [=]

Function: delete-duplicates! list [=]

Remove duplicate elements from the list argument. If there are multiple equal elements in 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(n2) 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))