`SET`

signatureThe `SET`

signature is an interface for a set type, which is
an unordered collection of items. Sets do not contain duplicates, and are
not polymorphic — the type of their elements is fixed by the
Key substructure. We use a number of notational
conventions which can be seen
here. For example,
we write $|x|$ for the number of elements in a set $x$, and the empty set is
denoted either $\{\}$ or $\emptyset$.

```
structure Key : EQKEY
structure Seq : SEQUENCE
type t
type set = t
val size : set → int
val toString : set → string
val toSeq : set → Key.t Seq.t
val empty : unit → set
val singleton : Key.t → set
val fromSeq : Key.t Seq.t → set
val find : set → Key.t → bool
val insert : set * Key.t → set
val delete : set * Key.t → set
val filterKey : (Key.t → bool) → set → set
val reduceKey : (Key.t * Key.t → Key.t) → Key.t → set → Key.t
val iterateKey : (α * Key.t → α) → α → set → α
val union : set * set → set
val intersection : set * set → set
val difference : set * set → set
val $ : Key.t → set
```

`structure`

**Key**: EQKEY- The
`Key`

substructure defines the type of elements in a set, providing equality and other useful functions. `structure`

**Seq**: SEQUENCE- The
`Seq`

substructure defines the underlying sequence type to and from which sets can be converted.

`type`

**t**- The abstract set type.
`type`

**set**= t- An alias for
`t`

, for readability.

`val`

**size**: set → int`(size x)`

evaluates to $|x|$, the number of elements in the set $x$.`val`

**toString**: set → string-
`(toString x)`

evaluates to a string representation of $x$. Each element of $x$ is converted to a string by`Key.toString`

. For example, the set $\{1,2,3\}$ would be represented by the string “`{1,2,3}`

”. `val`

**toSeq**: set → Key.t Seq.t- Return the sequence containing all elements of a set. The ordering of the elements in the returned sequence is implementation defined.
`val`

**empty**: unit → set- Construct the empty set, $\{\}$.
`val`

**singleton**: Key.t → set-
`(singleton x)`

evaluates to $\{x\}$, the singleton set containing only the element $x$. `val`

**fromSeq**: Key.t Seq.t → set- Return the set containing all elements of a sequence.
`val`

**find**: set → Key.t → bool-
`(find x k)`

returns whether or not $k$ is a member of the set $x$. `val`

**insert**: set * Key.t → set-
`(insert (x, k))`

evaluates to the set $x \cup \{k\}$. `val`

**delete**: set * Key.t → set-
`(delete (x, k))`

evaluates to the set $x \setminus \{k\}$. `val`

**filterKey**: (Key.t → bool) → set → set-
`(filterKey p x)`

evaluates to the subset of $x$ containing every key $k$ which satisfies $p(k)$. `val`

**reduceKey**: (Key.t * Key.t → Key.t) → Key.t → set → Key.t-
`(reduceKey f b x)`

is logically equivalent to`(Seq.reduce f b (toSeq x))`

. `val`

**iterateKey**: (α * Key.t → α) → α → set → α-
`(iterateKey f b x)`

is logically equivalent to`(Seq.iterate f b (toSeq x))`

. `val`

**union**: set * set → set`(union (x, y))`

evaluates to the set $x \cup y$.`val`

**intersection**: set * set → set`(intersection (x, y))`

evaluates to the set $x \cap y$.`val`

**difference**: set * set → set`(difference (x, y))`

evaluates to the set $x \setminus y$.`val`

**$**: Key.t → set- An alias for
`singleton`

.