The SET signature

« 210 Library Documentation

Overview

The 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$.

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

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, 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.

Types

type t
The abstract set type.
type set = t
An alias for t, for readability.

Values

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.