Next: srfi list spec side, Previous: srfi list spec alist, Up: srfi list spec [Index]

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:- 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`:`(= 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.- If

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

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

Next: srfi list spec side, Previous: srfi list spec alist, Up: srfi list spec [Index]