The SET signature

« 210 Library Documentation

Overview

functor MkTreapTable

A set $S$ is a finite collection of unique elements of some type and the size of $S$, denoted by $|S|$, is the number of elements in that set. The crucial difference between a set in the mathematical sense and a set in this library is that a set here is always ordered implicitly for enumeration purposes. The empty set is denoted by $\emptyset$.

Interface

structure Key : EQKEY
structure Seq : SEQUENCE

type set
type key = Key.t

val size : set -> int
val toString : set -> string
val toSeq : set -> key Seq.seq

val empty : unit -> set
val singleton : key -> set
val fromSeq : key Seq.seq -> set

val find : set -> key -> bool
val insert : key -> set -> set
val delete : key -> set -> set

val filter : (key -> bool) -> set -> set

val union : set * set -> set
val intersection : set * set -> set
val difference : set * set -> set

type t = set
val $ : key -> set

Substructures

structure Key : EQKEY
The Key substructure defines the type of elements in a set, providing equality and toString functions on such elements.
structure Seq : SEQUENCE
The Seq substructure defines the underlying SEQUENCE type to and from which sets can be converted.

Types

type set
This is the abstract type that represents a set as described in the overview.
type key = Key.t
This indicates that the keys in a set must be of type Key.t.

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$. This representation begins with “{”, followed by the results of applying Key.toString to each element of $X$ in some order interleaved with “,”, and ends with “}”.
val toSeq : set -> key Seq.seq
(toSeq X) evaluates to a sequence containing all elements in the set $X$. The ordering of the sequence is implementation-defined.
val empty : unit -> set
(empty ()) evaluates to the empty set, $\emptyset$.
val singleton : key -> set
(singleton x) evaluates to the set containing only the element $x$.
val fromSeq : key Seq.seq -> set
If $S$ is an $n$-length sequence $\langle S_0,S_1,\ldots,S_{n-1}\rangle$, (fromSeq S) evaluates to the set $\{S_0,S_1,\ldots,S_{n-1}\}$. The ordering in the set representation may differ from the ordering in the sequence representation.
val find : set -> key -> bool
(find X k) evaluates to true if and only if $k$ is a memeber of the set $X$.
val insert : key -> set -> set
(insert k X) evaluates to the set $X\cup\{k\}$.
val delete : key -> set -> set
(delete k X) evaluates to the set $X\setminus\{k\}$.
val filter : (key -> bool) -> set -> set
(filter p X) evaluates to the subset $X'$ of $X$ such that an element $x\in X'$ if and only if $p(x)$ evaluates to true.
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$.