Lists can be used to represent sets of objects. The procedures in this section operate on such lists as sets.

Note that lists are not an efficient way to implement large sets. The
procedures here typically take time `m`x`n` when
operating on `m` and `n` element lists. Other data structures
like trees, bitsets (see Bit Vectors) or hash tables (see Hash Tables) are faster.

All these procedures take an equality predicate as the first argument.
This predicate is used for testing the objects in the list sets for
sameness. This predicate must be consistent with `eq?`

(see Equality) in the sense that if two list elements are
`eq?`

then they must also be equal under the predicate. This
simply means a given object must be equal to itself.

— Scheme Procedure: **lset<=**` = list1 list2 ...`

Return

`#t`

if each list is a subset of the one following it. Ie.list1a subset oflist2,list2a subset oflist3, etc, for as many lists as given. If only one list or no lists are given then the return is`#t`

.A list

xis a subset ofyif each element ofxis equal to some element iny. Elements are compared using the given=procedure, called as`(`

=`xelem yelem)`

.(lset<= eq?) ⇒ #t (lset<= eqv? '(1 2 3) '(1)) ⇒ #f (lset<= eqv? '(1 3 2) '(4 3 1 2)) ⇒ #t

— Scheme Procedure: **lset=**` = list1 list2 ...`

Return

`#t`

if all argument lists are set-equal.list1is compared tolist2,list2tolist3, etc, for as many lists as given. If only one list or no lists are given then the return is`#t`

.Two lists

xandyare set-equal if each element ofxis equal to some element ofyand conversely each element ofyis equal to some element ofx. The order of the elements in the lists doesn't matter. Element equality is determined with the given=procedure, called as`(`

=`xelem yelem)`

, but exactly which calls are made is unspecified.(lset= eq?) ⇒ #t (lset= eqv? '(1 2 3) '(3 2 1)) ⇒ #t (lset= string-ci=? '("a" "A" "b") '("B" "b" "a")) ⇒ #t

— Scheme Procedure: **lset-adjoin**` = list elem1 ...`

Add to

listany of the givenelems not already in the list.elems are`cons`

ed onto the start oflist(so the return shares a common tail withlist), but the order they're added is unspecified.The given

=procedure is used for comparing elements, called as`(`

=`listelem elem)`

, ie. the second argument is one of the givenelemparameters.(lset-adjoin eqv? '(1 2 3) 4 1 5) ⇒ (5 4 1 2 3)

— Scheme Procedure: **lset-union**` = list1 list2 ...`

— Scheme Procedure:**lset-union!**` = list1 list2 ...`

— Scheme Procedure:

Return the union of the argument list sets. The result is built by taking the union of

list1andlist2, then the union of that withlist3, etc, for as many lists as given. For one list argument that list itself is the result, for no list arguments the result is the empty list.The union of two lists

xandyis formed as follows. Ifxis empty then the result isy. Otherwise start withxas the result and consider eachyelement (from first to last). Ayelement not equal to something already in the result is`cons`

ed onto the result.The given

=procedure is used for comparing elements, called as`(`

=`relem yelem)`

. The first argument is from the result accumulated so far, and the second is from the list being union-ed in. But exactly which calls are made is otherwise unspecified.Notice that duplicate elements in

list1(or the first non-empty list) are preserved, but that repeated elements in subsequent lists are only added once.(lset-union eqv?) ⇒ () (lset-union eqv? '(1 2 3)) ⇒ (1 2 3) (lset-union eqv? '(1 2 1 3) '(2 4 5) '(5)) ⇒ (5 4 1 2 1 3)

`lset-union`

doesn't change the given lists but the result may share a tail with the first non-empty list.`lset-union!`

can modify all of the given lists to form the result.

— Scheme Procedure: **lset-intersection**` = list1 list2 ...`

— Scheme Procedure:**lset-intersection!**` = list1 list2 ...`

— Scheme Procedure:

Return the intersection of

list1with the other argument lists, meaning those elements oflist1which are also in all oflist2etc. For one list argument, just that list is returned.The test for an element of

list1to be in the return is simply that it's equal to some element in each oflist2etc. Notice this means an element appearing twice inlist1but only once in each oflist2etc will go into the return twice. The return has its elements in the same order as they were inlist1.The given

=procedure is used for comparing elements, called as`(`

=`elem1 elemN)`

. The first argument is fromlist1and the second is from one of the subsequent lists. But exactly which calls are made and in what order is unspecified.(lset-intersection eqv? '(x y)) ⇒ (x y) (lset-intersection eqv? '(1 2 3) '(4 3 2)) ⇒ (2 3) (lset-intersection eqv? '(1 1 2 2) '(1 2) '(2 1) '(2)) ⇒ (2 2)The return from

`lset-intersection`

may share a tail withlist1.`lset-intersection!`

may modifylist1to form its result.

— Scheme Procedure: **lset-difference**` = list1 list2 ...`

— Scheme Procedure:**lset-difference!**` = list1 list2 ...`

— Scheme Procedure:

Return

list1with any elements inlist2,list3etc removed (ie. subtracted). For one list argument, just that list is returned.The given

=procedure is used for comparing elements, called as`(`

=`elem1 elemN)`

. The first argument is fromlist1and the second from one of the subsequent lists. But exactly which calls are made and in what order is unspecified.(lset-difference eqv? '(x y)) ⇒ (x y) (lset-difference eqv? '(1 2 3) '(3 1)) ⇒ (2) (lset-difference eqv? '(1 2 3) '(3) '(2)) ⇒ (1)The return from

`lset-difference`

may share a tail withlist1.`lset-difference!`

may modifylist1to form its result.

— Scheme Procedure: **lset-diff+intersection**` = list1 list2 ...`

— Scheme Procedure:**lset-diff+intersection!**` = list1 list2 ...`

— Scheme Procedure:

Return two values (see Multiple Values), the difference and intersection of the argument lists as per

`lset-difference`

and`lset-intersection`

above.For two list arguments this partitions

list1into those elements oflist1which are inlist2and not inlist2. (But for more than two arguments there can be elements oflist1which are neither part of the difference nor the intersection.)One of the return values from

`lset-diff+intersection`

may share a tail withlist1.`lset-diff+intersection!`

may modifylist1to form its results.

— Scheme Procedure: **lset-xor**` = list1 list2 ...`

— Scheme Procedure:**lset-xor!**` = list1 list2 ...`

— Scheme Procedure:

Return an XOR of the argument lists. For two lists this means those elements which are in exactly one of the lists. For more than two lists it means those elements which appear in an odd number of the lists.

To be precise, the XOR of two lists

xandyis formed by taking those elements ofxnot equal to any element ofy, plus those elements ofynot equal to any element ofx. Equality is determined with the given=procedure, called as`(`

=`e1 e2)`

. One argument is fromxand the other fromy, but which way around is unspecified. Exactly which calls are made is also unspecified, as is the order of the elements in the result.(lset-xor eqv? '(x y)) ⇒ (x y) (lset-xor eqv? '(1 2 3) '(4 3 2)) ⇒ (4 1)The return from

`lset-xor`

may share a tail with one of the list arguments.`lset-xor!`

may modifylist1to form its result.