A set is an unordered collection of values without duplicates. FSet imposes an ordering for its own purposes, but you should not expect that ordering to be predictable.
The simplest way to create a set is with the function empty-set:
> (defparameter es (empty-set))
ES
> es
##{ }
Now we can add an element to the set with with:
> (defparameter s (with es 3))
S
> s
##{ 3 }
You can see that the with function has returned a new set without modifying the original:
> es
##{ }
The function empty? tells you whether a set is empty. (FSet uses the trailing question mark
rather than the older -p convention for the names of boolean-valued functions.)
> (empty? s) NIL > (empty? es) T
If the set is not empty, arb will give you an arbitrary one of its elements:
> (arb s) 3 T
Note that arb is not guaranteed to give you any particular element, nor is its job to give you
a “randomly selected” element. Its only postcondition is to give you some element of the set.
This contract may seem a bit odd, but it gives the implementation flexibility to return a
“convenient” element. And it’s still usable in algorithms. For one thing, if the set is a singleton
(has size 1), then arb is guaranteed to return the only element. For another, some “workset”
algorithms don’t need a particular element; they just need to pull some element out of the set on each
loop iteration until it’s empty. (Example below.)
(The second value of T indicates that the set was, in fact, nonempty; FSet’s philosophy is to
use multiple values to indicate special cases, when that makes sense, instead of signalling errors.)
Having obtained an element of the set, we can remove it with less:
> (less s 3)
##{ }
This may not seem too exciting yet, but it is already enough to write certain algorithms which have this general form:
(let ((workset (some-set)))
(loop while (not (empty? workset))
(let ((x (arb workset)))
(setq workset (less workset x))
(some-operation-on x)
(dolist (y (successors-of-some-kind x))
(if (some-predicate y)
(setq workset (with workset y)))))))
Another important function on sets is size, which returns the number of elements:
> (size s) 1
To test membership of a particular value, there’s contains?:
> (contains? s 2) NIL > (contains? s 3) T
Constructing literal sets by repeated applications of with gets tedious, so FSet provides a
constructor macro which is simply called set. (We have shadowed cl:set, which is
archaic anyway, in the fset-user package.) For example:
> (set)
##{ }
> (defparameter s1 (set 1 2 3))
S1
> s1
##{ 1 2 3 }
> (defparameter s2 (set 'c 1 "foo" 'a 'c))
S2
> s2
##{ 1 C A "foo" }
(The order in which set and map elements are printed can depend on which Common Lisp implementation you are running on.)
You can see that FSet handles many builtin Lisp types (we’ll get to the whole list later); that mixing types in a collection is no problem, of course, this being Lisp; that sets ignore duplication of elements; and that FSet imposes its own ordering on sets.
The set constructor macro has a syntax for including all the elements of another set (this is
why it’s a macro):
> (set ($ s1) 'x)
##{ 1 2 3 X }
Given a couple of sets, we can start to do some more interesting things with them:
> (equal? s1 (set 3 2 1))
T
> (union s1 s2)
##{ 1 2 3 C A "foo" }
> (intersection s1 s2)
##{ 1 }
> (set-difference s1 s2)
##{ 2 3 }
> (set-difference-2 s1 s2)
##{ 2 3 }
##{ C A "foo" }
(That last one is returning both differences as two values.)
FSet provides alternate versions of many CL functions, which are intended to be shadowing-imported
into your code package (and are, obviously, in fset-user). Most of these are CLOS generic
functions, with compatibility methods so they will do the same thing as the CL builtins if invoked
on non-FSet types. However, you see we have a separate predicate equal? rather than
shadowing cl:equal.
There are also a couple of useful predicates on pairs of sets:
> (subset? (set 1 2) s1) T > (subset? s1 (set 1 2)) NIL > (disjoint? s1 (set 1 2)) NIL > (disjoint? s1 (set 4 5)) T