`AUG_BST`

signature
The `AUG_BST`

signature is an interface for an augmented binary
search tree with fixed key and value types. This signature is nearly
identical to `BST`

except for the addition
of `reduceVal`

, the
`Val`

substructure, and the lack of
polymorphism.

```
structure Key : ORDKEY
structure Val : MONOID
type t
type bst = t
datatype view =
LEAF
| NODE of { key : Key.t
, value : Val.t
, left : bst
, right : bst }
val expose : bst → view
val size : bst → int
val reduceVal : bst -> Val.t
val empty : unit → bst
val singleton : Key.t * Val.t → bst
val join : bst * bst → bst
val joinMid : bst * (Key.t * Val.t) * bst → bst
val split : bst * Key.t → bst * Val.t option * bst
val $ : Key.t * Val.t → bst
```

`structure`

**Key**: ORDKEY-
The
`Key`

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

**Val**: MONOID-
The
`Val`

substructure defines the value type of a binary search tree. It also contains values $f$ and $I$, which are a reducing function and corresponding identity such that`Val`

is a monoid. These values are using to maintain a reduced value which can be retrieved via`reduceVal`

.

`type`

**t**- The abstract tree type.
`type`

**bst**= t- An alias, for readability.
`type`

**view**= LEAF | NODE of {key : Key.t, value : Val.t, left : bst, right : 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.

`val`

**expose**: bst → view- Expose a view of the root node of the tree.
`val`

**size**: bst → int- Return the number of nodes in the tree.
`val`

**reduceVal**: bst → Val.t- Return the reduced value of the tree, which is logically equivalent to
a reduce over the values of the tree with
`Val.f`

as the reducing function and`Val.I`

as the identity. `val`

**empty**: unit → bst- Construct an empty tree.
`val`

**singleton**: Key.t * Val.t → bst- Construct a tree containing a single node with the given key and value.
`val`

**join**: bst * bst → bst- Given trees $A$ and $B$ where all keys in $A$ are strictly less
than all keys in $B$,
`(join (A, B))`

evaluates to the union of $A$ and $B$. `val`

**joinMid**: bst * (Key.t * Val.t) * bst → bst`(joinMid (A, (k, v), B))`

is logically equivalent to`(join (A, join (singleton (k, v), B))).`

`val`

**split**: bst * Key.t → bst * Val.t option * bst`(split (T, k))`

evaluates to $(L, x, R)$ where $L$ is a bst containing all keys less than $k$, $R$ is a bst containing all keys greater than $k$, and $x$ is the value associated with $k$ (or`NONE`

, if $k \not\in T$).`val`

**$**: Key.t * Val.t → bst- An alias for
`singleton`

.