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 mxn 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.
Return #t if each list is a subset of the one following it.
I.e., list1 is a subset of list2, list2 is a subset of
list3, etc., for as many lists as given. If only one list or no
lists are given, the return value is #t.
A list x is a subset of y if each element of x is
equal to some element in y. 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
Return #t if all argument lists are set-equal. list1 is
compared to list2, list2 to list3, etc., for as many
lists as given. If only one list or no lists are given, the return
value is #t.
Two lists x and y are set-equal if each element of x
is equal to some element of y and conversely each element of
y is equal to some element of x. 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
Add to list any of the given elems not already in the list.
elems are consed onto the start of list (so the
return value shares a common tail with list), but the order that
the elems are added is unspecified.
The given = procedure is used for comparing elements, called as
(= listelem elem), i.e., the second argument is one of
the given elem parameters.
(lset-adjoin eqv? '(1 2 3) 4 1 5) ⇒ (5 4 1 2 3)
Return the union of the argument list sets. The result is built by taking the union of list1 and list2, then the union of that with list3, 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 x and y is formed as follows. If
x is empty then the result is y. Otherwise start with
x as the result and consider each y element (from first to
last). A y element not equal to something already in the result
is consed 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.
Return the intersection of list1 with the other argument lists, meaning those elements of list1 which are also in all of list2 etc. For one list argument, just that list is returned.
The test for an element of list1 to be in the return is simply that it’s equal to some element in each of list2 etc. Notice this means an element appearing twice in list1 but only once in each of list2 etc will go into the return twice. The return has its elements in the same order as they were in list1.
The given = procedure is used for comparing elements, called as
(= elem1 elemN). The first argument is from list1
and 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 with
list1. lset-intersection! may modify list1 to form
its result.
Return list1 with any elements in list2, list3 etc 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 from list1
and 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 with
list1. lset-difference! may modify list1 to form
its result.
Return two values (see Returning and Accepting Multiple Values), the difference and
intersection of the argument lists as per lset-difference and
lset-intersection above.
For two list arguments this partitions list1 into those elements of list1 which are in list2 and not in list2. (But for more than two arguments there can be elements of list1 which are neither part of the difference nor the intersection.)
One of the return values from lset-diff+intersection may share
a tail with list1. lset-diff+intersection! may modify
list1 to form its results.
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 x and y is formed by
taking those elements of x not equal to any element of y,
plus those elements of y not equal to any element of x.
Equality is determined with the given = procedure, called as
(= e1 e2). One argument is from x and the other
from y, 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 modify list1 to form its
result.