# (lispkit list set)
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*.
```scheme
(lset<=? eq? '(a) '(a b a) '(a b c c)) ⇒ #t
(lset<=? eq?) ⇒ #t
(lset<=? eq? '(a b)) ⇒ #t
```
**(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*.
```scheme
(lset=? eq? '(b e a) '(a e b) '(e e b a)) ⇒ #t
(lset=? eq?) ⇒ #t
(lset=? eq? '(a b)) ⇒ #t
```
**(lset-contains? *****= xs x*****)**
Returns `#t` if element *x* is contained in *xs* using equality predicate *=* for comparing elements. Otherwise, `#f` is returned.
```scheme
(lset-contains? eq? '(a b c) 'b) ⇒ #t
(lset-contains? eq? '(a b c) 'd) ⇒ #f
(lset-contains? eq? '() 'd) ⇒ #f
```
**(lset-adjoin *****= xs x ...*****)**
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.
```scheme
(lset-adjoin eq? '(a b c d c e) 'a 'e 'i 'o) ⇒ (o i a b c d c e)
```
**(lset-union *****= xs ...*****)**
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 ...*.
```scheme
(lset-union eq? '(a b c d e) '(a e i o)) ⇒ (o i a b c d e)
(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-intersection *****= 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.
```scheme
(lset-intersection eq? '(a b c d e) '(a e i o u)) ⇒ (a e)
(lset-intersection eq? '(a x y a) '(x a x z)) ⇒ (a x a)
(lset-intersection eq? '(a b c)) ⇒ (a b c)
```
**(lset-difference *****= xs ...*****)**
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.
```scheme
(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-xor *****= xs ...*****)**
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 ...*.
```scheme
(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-diff+intersection *****= 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*.
```scheme
(values
(lset-difference = xs ...)
(lset-intersection = xs1 (lset-union = xs2 ...)))
```
***
Some of this documentation is derived from [SRFI 1](https://github.com/objecthub/lisppad-site/blob/gitbook/libraries/lispkit/\[https:/srfi.schemers.org/srfi-1/srfi-1.html#lset%3C=]\(https://srfi.schemers.org/srfi-1/srfi-1.html#lset%3C=\)) by Olin Shivers.