The `BST` signature

Overview

The BST signature is a minimalistic interface for a binary search tree, which is a set of key-value pairs. The key type is ordered and fixed by the Key substructure while the value type is polymorphic.

Interface

structure Key : ORDKEY

type 'a t
type 'a bst = 'a t

datatype 'a view =
LEAF
| NODE of { key : Key.t
				, value : 'a
				, left : 'a bst
				, right : 'a bst }

exception Order

val expose : 'a bst → 'a view
val size : 'a bst → int

val empty : unit → 'a bst
val singleton : Key.t * 'a → 'a bst

val join : 'a bst * 'a bst → 'a bst
val joinMid : 'a bst * (Key.t * 'a) * 'a bst → 'a bst

val split : 'a bst * Key.t → 'a bst * 'a option * 'a bst

val $ : Key.t * 'a → 'a bst

Substructures

structure Key : ORDKEY: The Key substructure defines the key type of a binary search tree, providing comparison and other useful functions on keys.

Types

type 'a t
type 'a bst = 'a t: The abstract tree type 'a t maps keys of type Key.t to values of type 'a. The alias 'a bst is for readability.
type 'a view = LEAF | NODE of {key : Key.t, value : 'a, left : 'a bst, right : 'a bst}: A one-layer view of a tree, which is either a leaf (containing no data) or an interior node with a key, value, and two children.

Exceptions

exception Order: Order is raised when the ordering invariant would be violated.

Values

val expose : 'a bst → 'a view: View the root node of the tree.
val size : 'a bst → int: Return the number of nodes in the tree.
val empty : unit → 'a bst: Construct an empty tree.
val singleton : Key.t * 'a → 'a bst: Construct a tree containing a single node with the given key and value.
val join : 'a bst * 'a bst → 'a bst: Given trees $A$ and $B$ where the largest key in $A$ is strictly smaller than the smallest key in $B$, join (A,B) is the union of all key-value pairs from both $A$ and $B$. Raises Order otherwise.
val joinMid : 'a bst * (Key.t * 'a) * 'a bst → 'a bst: joinMid (A, (k, v), B) is logically equivalent to join (A, join (singleton (k, v), B)).
val split : 'a bst * Key.t → 'a bst * 'a option * 'a bst: split (T, k) evaluates to $(L, v, R)$ where $L$ is a bst containing all keys from $T$ which are smaller than $k$, $R$ is a bst containing all keys larger than $k$, and $v$ is the value associated with $k$ (or NONE if $k$ is not in $T$).
val $ : Key.t * 'a → 'a bst: An alias for singleton.

The BST signature