Set

_Set_
_set_

This collection provides two files:

 _set.ss_: functional sets, with elements compared via `equal?'
 _seteq.ss_: functional sets, with elements compared via `eq?'

The data structures of this library are immutable. They are
implemented on top of PLT Scheme's immutable hash tables, and
therefore generally have O(1) running time for extending and
O(log n) running time for lookup.

This library was inspired by SRFI 1 [1] and GHC [2].

[1] SRFI-1. http://srfi.schemers.org/srfi-1/srfi-1.html
[2] Data.Set. http://www.haskell.org/ghc/docs/latest/html/libraries/containers/Data-Set.html

======================================================================

> type (setof a)

Sets of elements of type a, compared via `equal?'.

> type (seteqof a)

Sets of elements of type a, compared via `eq?'.

======================================================================

Both set.ss and seteq.ss provide exactly the same bindings.

> (set? x) :: any -> boolean

Determines whether a value is of the set type provided by this module.

> (list->set ls) :: (listof a) -> (set[eq]of a)

Produces a set of the elements in the given list.

> (set->list s) :: (set[eq]of a) -> (listof a)

Produces a list of the elements in the given set.

> empty :: (set[eq]of a)

An empty set.

> (empty? s) :: (set[eq]of a) -> boolean

Determines whether the given set is empty.

> (intersection s [ss ...]) :: (set[eq]of a) [(set[eq]of a) ...] -> (set[eq]of a)

Produces the intersection of the given sets.

> (intersections ss) :: (nelistof (set[eq]of a)) -> (set[eq]of a)

Produces the intersection of the given list of sets.

> (difference s [ss ...]) :: (set[eq]of a) [(set[eq]of a) ...] -> (set[eq]of a)

Produces the set difference of the given sets, left-associatively.

> (differences ss) :: (listof (set[eq]of a)) -> (set[eq]of a)

Produces the set difference of the given list of sets, left-associatively.

> (union [ss ...]) :: [(set[eq]of a) ...] -> (set[eq]of a)

Produces the union of the given sets.

> (unions ss) :: (listof (set[eq]of a)) -> (set[eq]of a)

Produces the union of the given list of sets.

> (xor s [ss ...]) :: (set[eq]of a) [(set[eq]of a) ...] -> (set[eq]of a)

Produces the exclusive union of the given sets. This operation is
associative and extends to the n-ary case -- the elements that
appear in an odd number of the sets.

> (partition s [ss ...]) :: (set[eq]of a) [(set[eq]of a) ...] -> (set[eq]of a) (set[eq]of a)

Equivalent to

    (values (difference s ss ...)
            (intersection s (union ss ...)))

but implemented more efficiently.

Note that this is ***NOT NECESSARILY THE SAME THING*** as

    (values (difference s ss ...)
            (intersection s ss ...)) ; NOT THE SAME THING!!!


> (adjoin s [x ...]) :: (set[eq]of a) [a ...] -> (set[eq]of a)

Produces a set containing the elements of s and the given element(s).

> (add x s) :: a (set[eq]of a) -> (set[eq]of a)

Produces a set containing x and the elements of s.

> (contains? s x) :: (set[eq]of a) a -> boolean

Determines whether the given set contains the given element, using
the relevant equality predicate.

> (for/set (for-clause ...) body ...+) :: syntax
> (for*/set (for-clause ...) body ...+) :: syntax

Like for/list and for*/list, respectively, but the result is a
set[eq]. The expression in the bodys must return a single value:
the value to extend the set accumulated by the iteration.