23.15 Set operations on lists

These procedures implement operations on sets represented as lists of elements. They all take an item= argument used to compare elements of lists; this equality procedure is required to be consistent with eq?; that is, it must be the case that:

(eq? x y) ⇒ (= x y)

Note that this implies, in turn, that two lists that are eq? are also set–equal by any legal comparison procedure. This allows for constant–time determination of set operations on eq? lists.

Be aware that these procedures typically run in time O(n * m) for n and m elements list arguments. Performance–critical applications operating upon large sets will probably wish to use other data structures and algorithms.

Function: lset<=? item= ell ...

Return true if, and only if, every elli is a subset of elli+1. List AL is a subset of list BL if every element in AL is equal to some element of BL. When performing an element comparison, the item= procedure’s first argument is an element of AL, its second argument an element of BL.

(lset<=? eq? '(a) '(a b a) '(a b c c))
⇒ #t

(lset<=? eq?)
⇒ #t

(lset<=? eq? '(a))
⇒ #t

If invoked with all null lists, the return value is #t.

Function: lset=? item= ell ...

Return true if, and only if, every elli is set–equal to elli+1. “Set–equal” simply means that elli is a subset of elli+1, and elli+1 is a subset of elli. The item= procedure’s first argument is an element of elli, its second argument is an element of elli+1.

(lset=? eq? '(b e a) '(a e b) '(e e b a))
⇒ #t

(lset=? eq?)
⇒ #t

(lset=? eq? '(a))
⇒ #t

Function: lset-adjoin item= ell0 ell ...

Add the Ei elements from the ell ... arguments, not already in ell0, to the result list. The result shares a common tail with the ell argument. The new elements are added to the front of the list, but no guarantees are made about their order.

item= is an equality procedure used to determine if an Ei is already a member of ell0; its first argument is an element of ell0, its second is one of the Ei.

The ell0 parameter is always a suffix of the result; even if the list parameter contains repeated elements, these are not reduced.

(lset-adjoin eq? '(a b c d c e) 'a 'e 'i 'o 'u)
⇒ (u o i a b c d c e)

Function: lset-union item= ell ...

Function: lset-union! item= ell ...

Return the union of the lists. The union of lists AL and BL is constructed as follows:

1. If AL is the empty list, the answer is BL (or a copy of BL).
2. Otherwise, the result is initialised to be list AL (or a copy of AL).
3. Proceed through the elements of list BL in a left–to–right order. If b is such an element of BL, compare every element r of the current result list to b: (item= r b). If all comparisons fail, b is consed onto the front of the result.

However, there is no guarantee that item= will be applied to every pair of arguments from AL and BL. In particular, if AL is eq? to BL, the operation may immediately terminate.

In the N–ary case, the two–argument list-union operation is simply folded across the argument lists.

(lset-union eq? '(a b c d e) '(a e i o u))
⇒ (u o i a b c d e)

;; Repeated elements in the first argument are preserved.
(lset-union eq? '(a a c) '(x a x))
⇒ (x a a c)

(lset-union eq?)
⇒ ()

(lset-union eq? '(a b c))
⇒ (a b c)

lset-union! is allowed to use the cons cells in the first list parameter to construct its answer; lset-union! is permitted to recycle cons cells from any of its list arguments.

Function: lset-intersection item= ell0 ell ...

Function: lset-intersection! item= ell0 ell ...

Return the intersection of the lists. The intersection of lists AL and BL is comprised of every element of AL that is item= to some element of BL: (item= a b), for a in AL, and b in BL. Note this implies that an element which appears in BL and multiple times in list AL will also appear multiple times in the result.

The order in which elements appear in the result is the same as they appear in ell0; that is, lset-intersection essentially filters ell0, without disarranging element order. The result may share a common tail with ell0.

In the N–ary case, the two–argument list-intersection operation is simply folded across the argument lists. However, the dynamic order in which the applications of item= are made is not specified.

(lset-intersection eq? '(a b c d e) '(a e i o u))
⇒ (a e)

;; Repeated elements in the first argument are preserved.
(lset-intersection eq? '(a x y a) '(x a x z))
⇒ '(a x a)

(lset-intersection eq? '(a b c))
⇒ (a b c)

lset-intersection! is allowed to use the cons cells in the first list parameter to construct its answer.

Function: lset-difference item= ell0 ell ...

Function: lset-difference! item= ell0 ell ...

Return the difference of the lists: All the elements of ell0 that are not item= to any element from one of the other ell parameters.

The item= procedure’s first argument is always an element of ell0; its second is an element of one of the other ell. The dynamic order in which the applications of item= are made is not specified. Elements that are repeated multiple times in the ell0 parameter will occur multiple times in the result.

The order in which elements appear in the result is the same as they appear in ell0; that is, lset-difference essentially filters ell0, without disarranging element order. The result may share a common tail with ell0.

(lset-difference eq? '(a b c d e) '(a e i o u))
⇒ (b c d)

(lset-difference eq? '(a b c))
⇒ (a b c)

lset-difference! is allowed to use the cons cells in the first list parameter to construct its answer.

Function: lset-xor item= ell ...

Function: lset-xor! item= ell ...

Return the exclusive–or of the sets. If there are exactly two lists, this is all the elements that appear in exactly one of the two lists. The operation is associative, and thus extends to the N–ary case, in which the result is a list of the elements that appear in an odd number of the lists. The result may share a common tail with any of the ell parameters.

More precisely, for two lists AL and BL, AL xor BL is a list of:

• Every element a of AL such that there is no element b of BL such that (item= a b), and
• Every element b of BL such that there is no element a of AL such that (item= b a).

In the n–ary case, the binary–xor operation is simply folded across the lists.

(lset-xor eq? '(a b c d e) '(a e i o u))
⇒ (d c b i o u)

(lset-xor eq?)
⇒ ()

(lset-xor eq? '(a b c d e))
⇒ (a b c d e)

lset-xor! is allowed to use the cons cells in the first list parameter to construct its answer.

Function: lset-diff+intersection item= ell0 ell ...

Function: lset-diff+intersection! item= ell0 ell ...

Return two values: The difference and the intersection of the lists. It is equivalent to:

(values (lset-difference = list1 list2 ...)
        (lset-intersection = list1
                             (lset-union = list2 ...)))

but can be implemented more efficiently.

The item= procedure’s first argument is an element of ell0; its second is an element of one of the other ell arguments.

Either of the returned lists may share a common tail with ell0. This operation essentially partitions ell0.

lset-diff+intersection! is allowed to use the cons cells in the first list argument to construct its answer.