Next: lists low, Previous: lists circ, Up: lists [Index]

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:- If
`AL`is the empty list, the answer is`BL`(or a copy of`BL`). - Otherwise, the result is initialised to be list
`AL`(or a copy of`AL`). - 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.- If

- 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.- Every element

- 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.

Next: lists low, Previous: lists circ, Up: lists [Index]