(lispkit list set)
Last updated
Last updated
Library (lispkit list set) provides a simple API for list-based sets, called lset. Such sets are simply represented as lists (without duplicate entries) with respect to a given equality relation. Every lset procedure is provided as its first argument such an equality predicate. It is up to the client of the API to make sure that equality predicate and the given list-based sets are compatible and are used consistently.
An equality predicate = is required to be consistent with eq?, i.e. it must satisfy (eq? x y) ⇒ (= x y). This implies, in turn, that two lists that are eq? are also set-equal by any compliant comparison procedure. This allows for constant-time determination of set operations on eq? lists.
(lset = x ...)
Returns a list-based set containing all the elements x ... without duplicates when using equality predicate = for comparing elements.
(list->lset = xs)
Returns a list-based set containing all the elements of list xs without duplicates when using equality predicate = for comparing elements.
(lset<=? = xs ...)
Returns #t iff every list xsi is a subset of list xsi+1 using equality predicate = for comparing elements, otherwise #f is returned. List A is a subset of list B if every element in A is equal to some element of B. When performing an element comparison, the = procedure's first argument is an element of A, its second argument is an element of B.
(lset=? = xs ...)
Returns #t iff every list xsi is set-equal to xsi+1 using equality predicate = for comparing elements, otherwise #f is returned. "Set-equal" simply means that xsi is a subset of xsi+1, and xsi+1 is a subset of xsi. When performing an element comparison, the = procedure's first argument is an element of xsi, its second argument is an element of xsi+1.
(lset-contains? = xs x)
Returns #t if element x is contained in xs using equality predicate = for comparing elements. Otherwise, #f is returned.
Adds the elements x ... not already in the list xs and returns the result as a list. The new elements are added to the front of the list, but no guarantees are made about their order. The = parameter is an equality predicate used to determine if an element x is already a member of xs. Its first argument is an element of xs; its second is one of the x ... elements. xs is always a suffix of the result returned by lset-adjoin, even if xs contains repeated elements, these are not reduced.
Returns the union of the lists xs using equality predicate = for comparing elements. The union of lists A and B is constructed as follows:
If A is the empty list, the answer is B
Otherwise, the result is initialised to be list A
Proceed through the elements of list B in a left-to-right order. If b is such an element of B, 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.
In the n-ary case, the two-argument list-union operation is simply folded across the argument lists xs ....
Returns the intersection of the lists xs using equality predicate = for comparing elements.
The intersection of lists A and B is comprised of every element of A that is = to some element of B: (= a b), for a in A, and b in B. This implies that an element which appears in B and multiple times in list A will also appear multiple times in the result.
The order in which elements appear in the result is the same as they appear in xs1, i.e. lset-intersection essentially filters xs1, without disarranging element order.
In the n-ary case, the two-argument lset-intersection operation is simply folded across the argument lists.
Returns the difference of the lists xs ... using equality predicate = for comparing elements. The result is a list of all the elements of xs1 that are not = to any element from one of the other xsi lists.
The = procedure's first argument is always an element of xs1 whereas its second argument is an element of one of the other xsi. Elements that are repeated multiple times in xs1 will occur multiple times in the result. The order in which elements appear in the result list is the same as they appear in xs1, i.e. lset-difference essentially filters xs1, without disarranging element order.
Returns the exclusive-or of the list-based sets xs ... using equality predicate = for comparing elements. 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.
More precisely, for two lists A and B, A "xor" B is a list of
every element a of A such that there is no element b of B such that (= a b), and
every element b of B such that there is no element a of A such that (= b a).
However, an implementation is allowed to assume that = is symmetric, i.e., that (= a b) ⇒ (= b a). This means, e.g. that if a comparison (= a b) returns #t for some a in A and b in B, 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 xs ....
Returns two values: the difference and the intersection of the list-based sets xs ... using equality predicate = for comparing elements. Is equivalent to but can be implemented more efficiently than the code below. The = procedure's first argument is an element of xs1, its second arguments is an element of one of the other xsi. lset-diff+intersection essentially partitions xs1 into elements that are unique to xs1 and elements that are shared with other xsi.
Some of this documentation is derived from SRFI 1 by Olin Shivers.
(lset-adjoin = xs x ...)
(lset-union = xs ...)
(lset-intersection = xs ...)
(lset-difference = xs ...)
(lset-xor = xs ...)
(lset-diff+intersection = xs ...)
