The SET signature

Overview

The SET interface specifies an unordered collection of items. Sets do not contain duplicates, and are not polymorphic: the type of their elements is given 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$.

Interface

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 : ('a * Key.t → 'a) → 'a → set → 'a

val union : set * set → set
val intersection : set * set → set
val difference : set * set → set

val $ : Key.t → set

Substructures

structure Key : EQKEY

The Key substructure defines the type of elements in a set, which may be compared for equality.

structure Seq : SEQUENCE

The Seq substructure defines the underlying sequence type, so that we may convert sets to and from sequences.

Types

type t

type set = t

The abstract set type. The alias set is for readability in the signature.

Values

val size : set → int

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

val toString : set → string

Evaluates to a string representation of the set. Each element is converted to a string via Key.toString.

val toSeq : set → Key.t Seq.t

Return the sequence containing all keys in 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

Construct the singleton set containing only the provided key.

val fromSeq : Key.t Seq.t → set

Return the set of 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 : ('a * Key.t → 'a) → 'a → set → 'a

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.