The AUG_BST signature

« 15-210 SML Library Documentation

Overview

The AUG_BST signature is an interface for an augmented binary search tree with fixed key and value types. It is identical to BST except for the type value of its values, which takes the place of 'a, the values combine and identity, which say how values combine, and the addition of reducedVal. The operations shared with BST are described there.

Interface

structure Key : ORDKEY

type value
val combine : value * value → value
val identity : value

type t
type bst = t

type nodeview = { left : bst,
                  key : Key.t,
                  value : value,
                  right : bst }

exception Order

val empty : unit → bst
val size : bst → int
val expose : bst → nodeview option
val joinMid : bst * (Key.t * value) * bst → bst

val reducedVal : bst → value

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 value
The type of the values.
type t
The abstract tree type.
type bst = t
An alias, for readability.
type nodeview = { left : bst, key : Key.t, value : value, right : bst }
The root of a non-empty tree: its key and value, and its left and right subtrees.

Values

val combine : value * value → value
An associative function that combines two values.
val identity : value
The identity of combine: combining it with any value $x$, on either side, gives back $x$.
val reducedVal : bst → value
reducedVal T evaluates to $v_1 \oplus v_2 \oplus \cdots \oplus v_n$, where $v_1, \ldots, v_n$ are the values of $T$ in increasing order of their keys and $\oplus$ is combine. It evaluates to identity if $T$ is empty.