2.2.5.11 Set operations on lists

These procedures implement operations on sets represented as lists of elements. They all take an = 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–element list arguments. Performance–critical applications operating upon large sets will probably wish to use other data structures and algorithms.

Function: lset<= = list1 ...

Return true if, and only if, every listi is a subset of listi+1, using = for the element–equality procedure. 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 = procedure’s first argument is an element of AL, its second argument an element of BL.

Examples:

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

(lset<= eq?) => #t             ; Trivial cases
(lset<= eq? '(a)) => #t

Function: lset= = list1 list2 ...

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

Examples:

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

(lset= eq?) => #t               ; Trivial cases
(lset= eq? '(a)) => #t

Function: lset-adjoin = list elt1 ...

Add the elti elements not already in the list parameter to the result list. The result shares a common tail with the list parameter. The new elements are added to the front of the list, but no guarantees are made about their order. The = parameter is an equality procedure used to determine if an elti is already a member of list. Its first argument is an element of list, its second is one of the elti.

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

Example:

(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 = list1 ...

Function: lset-union! = list1 ...

Return the union of the lists, using = for the element–equality procedure.

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: (= r b). If all comparisons fail, b is consed onto the front of the result.

However, there is no guarantee that = 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.

Examples:

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

;; Repeated elements in LIST1 are preserved.
(lset-union eq? '(a a c) '(x a x)) => (x a a c)

;; Trivial cases
(lset-union eq?) => ()
(lset-union eq? '(a b c)) => (a b c)

lset-union! is the linear–update variant of lset-union. It is allowed, but not required, 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 = list1 list2 ...

Function: lset-intersection! = list1 ...

Return the intersection of the lists, using = for the element–equality procedure.

The intersection of lists AL and BL is comprised of every element of AL that is = to some element of BL: (= 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 list1; that is, lset-intersection essentially filters list1, without disarranging element order. The result may share a common tail with list1.

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 = are made is not specified. The procedure may check an element of list1 for membership in every other list before proceeding to consider the next element of list1, or it may completely intersect list1 and list2 before proceeding to list3, or it may go about its work in some third order.

Examples:

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

;; Repeated elements in LIST1 are preserved.
(lset-intersection eq? '(a x y a) '(x a x z))
  => '(a x a)

(lset-intersection eq? '(a b c))        ; Trivial case
  => (a b c)

lset-intersection! is the linear–update variant of lset-intersection. It is allowed, but not required, to use the cons cells in the first list parameter to construct its answer.

Function: lset-difference = list1 list2 ...

Function: lset-difference! = list1 ...

Return the difference of the lists, using = for the element–equality procedure: all the elements of list1 that are not = to any element from one of the other listi parameters.

The = procedure’s first argument is always an element of list1; its second is an element of one of the other listi. Elements that are repeated multiple times in the list1 parameter will occur multiple times in the result.

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

The dynamic order in which the applications of = are made is not specified. The procedure may check an element of list1 for membership in every other list before proceeding to consider the next element of list1, or it may completely compute the difference of list1 and list2 before proceeding to list3, or it may go about its work in some third order.

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

(lset-difference eq? '(a b c))   ; Trivial case
  => (a b c)

lset-difference! is the linear–update variant of lset-difference. It is allowed, but not required, to use the cons cells in the first list parameter to construct its answer.

Function: lset-xor = list1 ...

Function: lset-xor! = list1 ...

Return the exclusive–or of the sets, using = for the element–equality procedure. 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 listi 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 (= a b), and
• every element b of BL such that there is no element a of AL such that (= b a).

However, an implementation is allowed to assume that = is symmetric; that is, that (= a b) => (= b a).

This means, for example, that if a comparison (= a b) produces true for some a in AL and b in BL, both a and b may be removed from inclusion in the result.

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

Examples:

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

;; Trivial cases.
(lset-xor eq?) => ()
(lset-xor eq? '(a b c d e)) => (a b c d e)

lset-xor! is the linear–update variant of lset-xor. It is allowed, but not required, to use the cons cells in the first list parameter to construct its answer.

Function: lset-diff+intersection = list1 list2 ...

Function: lset-diff+intersection! = list1 list2 ...

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 = procedure’s first argument is an element of list1; its second is an element of one of the other listi.

Either of the answer lists may share a common tail with list1. This operation essentially partitions list1.

lset-diff+intersection! is the linear–update variant of lset-diff+intersection. It is allowed, but not required, to use the cons cells in the first list parameter to construct its answer.