The library provides binary search trees, sorted dictionaries and sorted sets,
in two layers. A binary search tree is the tree from lecture: you take it apart
at its root using expose and build new trees using join_mid.
A dictionary or set is built on a tree, but you use it through
operations on keys and values, such as find, insert
and union.
In each layer, a signature lists the operations and a functor builds a structure that has them. The library's functors build treaps, but code written against a signature, rather than a particular structure, is generic: it works with any structure that matches the signature. This page shows how to make each kind of structure and how to write generic code over it. The signature pages describe every operation in full.
A tree holds key-value pairs. Its keys are distinct and increase from left to
right, in the order given by Key.compare, where Key is
the tree's key structure. Its values can have any type. The
BST signature gives a tree four
operations:
val size : 'a bst -> int
val expose : 'a bst -> 'a nodeview option
val empty : unit -> 'a bst
val joinMid : 'a bst * (Key.t * 'a) * 'a bst -> 'a bst
expose is the primary mechanism for writing generic code over BSTs. It returns
a view of the root element: NONE for the
empty tree, and otherwise SOME of a record holding the root's key
and value and its two subtrees:
type 'a nodeview = { left : 'a bst,
key : Key.t,
value : 'a,
right : 'a bst }
joinMid (L, (k, v), R) works the other way, building one tree from
a left subtree, a key-value pair and a right subtree. It requires every key of
L to be less than k, and k to be less
than every key of R. This is where a balanced tree does its
balancing, so the result holds exactly those pairs but need not have
k at its root.
Every other tree algorithm, from searching to splitting to taking a union, can be written with these four operations.
MkTreap makes a tree structure
from a key structure. The library provides key structures for the basic types,
such as IntElt and StringElt. Trees are then built up
from empty with joinMid:
structure Tree = MkTreap (structure Key = IntElt)
fun leaf (k, v) = Tree.joinMid (Tree.empty (), (k, v), Tree.empty ())
val t = Tree.joinMid (leaf (1, "a"), (2, "b"), leaf (3, "c"))
A treap also has split and join, described on the
MkTreap page. They are not
part of BST, so generic code cannot use them.
MkAugTreap makes an
augmented tree, an AUG_BST. It
also takes the type of the values, a function that combines them and its
identity, and adds reducedVal, which works as it does for
augmented dictionaries.
Generic tree code is written as a functor that takes a structure matching
BST. It can use the four operations and nothing else, so it works
with any tree implementation. The usual shape is a recursion
that exposes the tree, handles the empty and non-empty cases, and then recurs
on the left or right subtree, or both.
functor MkMyTreeAlgorithms (structure Tree : BST) =
struct
(* SOME v if t maps k to v, and NONE otherwise *)
fun find (t : 'a Tree.bst) (k : Tree.Key.t) : 'a option =
case Tree.expose t of
NONE => NONE
| SOME {left, key, value, right} =>
case Tree.Key.compare (k, key) of
LESS => find left k
| EQUAL => SOME value
| GREATER => find right k
(* t with k mapped to v, replacing any value k already had *)
fun insert (t : 'a Tree.bst, (k : Tree.Key.t, v : 'a)) : 'a Tree.bst =
case Tree.expose t of
NONE => Tree.joinMid (Tree.empty (), (k, v), Tree.empty ())
| SOME {left, key, value, right} =>
case Tree.Key.compare (k, key) of
LESS => Tree.joinMid (insert (left, (k, v)), (key, value), right)
| EQUAL => Tree.joinMid (left, (k, v), right)
| GREATER => Tree.joinMid (left, (key, value), insert (right, (k, v)))
end
structure MyAlgorithms = MkMyTreeAlgorithms (structure Tree = Tree)
val t2 = MyAlgorithms.insert (t, (4, "d"))
val four = MyAlgorithms.find t2 4 (* SOME "d" *)
find only reads the tree, following one path down from the root.
insert follows the same path, then rebuilds it with
joinMid on the way back up. The new key always goes into the
subtree where it belongs, so every joinMid gets the ordering it
requires, and each one gives the tree a chance to rebalance.
A dictionary maps keys to values, and a set is a collection of keys. Their keys
are sorted by Key.compare, which gives meaning to operations such as
first, next, split and
getRange. The
SORTED_DICT signature lists
a dictionary's operations, and
SORTED_SET lists a set's:
the same operations without values, with contains in place of
find.
Like everything in the library, dictionaries and sets are persistent. An
operation such as insert returns a new dictionary and leaves its
argument unchanged, so the old version remains valid and can still be used.
MkTreapDict and
MkTreapSet
take a key structure, as MkTreap does, and use
ArraySequence for their sequences. The quickest way to fill a
dictionary is fromSeq, which accepts pairs in any order and keeps
the first value of a key that repeats:
structure Seq = ArraySequence
structure Dict = MkTreapDict (structure Key = IntElt)
structure Set = MkTreapSet (structure Key = IntElt)
(* Creates the dictionary {1 -> "a", 2 -> "b", 3 -> "c"} *)
val d = Dict.fromSeq (Seq.fromList [(3, "c"), (1, "a"), (3, "z"), (2, "b")])
(* Creates the set {1, 3, 5} *)
val s = Set.fromSeq (Seq.fromList [5, 1, 3, 1])
Generic dictionary code is written the same way, as a functor that takes a
structure matching SORTED_DICT. Inside the functor the dictionary
type is abstract: the code can use the signature's operations and nothing else,
so it works with whichever dictionary the functor is applied to.
For example, a histogram counts how many times each key has occurred.
It can be represented as a dictionary that maps each key to its count, with
three operations: empty makes a histogram in which nothing has
occurred, add records one more occurrence of a key, and
count returns how many times a key has occurred, which is 0 if it
never has:
functor MkHistogram (structure Dict : SORTED_DICT) =
struct
type histogram = int Dict.dict
fun empty () : histogram = Dict.empty ()
(* h with one more occurrence of k *)
fun add (h : histogram, k : Dict.Key.t) : histogram =
case Dict.find h k of
NONE => Dict.insert (h, (k, 1))
| SOME n => Dict.insert (h, (k, n + 1))
(* The number of times k has occurred in h *)
fun count (h : histogram) (k : Dict.Key.t) : int =
case Dict.find h k of
NONE => 0
| SOME n => n
end
Since insert replaces the value of a key that is already present,
add looks up the old count first and then inserts one more.
Applied to a dictionary with string keys, the histogram counts words:
structure Words = MkHistogram (structure Dict = MkTreapDict (structure Key = StringElt))
val h1 = Words.add (Words.empty (), "pear")
val h2 = Words.add (h1, "apple")
val h3 = Words.add (h2, "pear")
val pears = Words.count h3 "pear" (* 2 *)
val earlier = Words.count h1 "pear" (* 1, since h1 is unchanged *)
Generic set code takes a structure matching SORTED_SET instead.
These two tests, whether one set is a subset of another and whether two sets
have no keys in common, work with any set:
functor MkSetRelations (structure Set : SORTED_SET) =
struct
(* Whether every key of a is also in b *)
fun isSubset (a : Set.set, b : Set.set) : bool =
Set.size (Set.difference (a, b)) = 0
(* Whether a and b have no keys in common *)
fun isDisjoint (a : Set.set, b : Set.set) : bool =
Set.size (Set.intersection (a, b)) = 0
end
An augmented dictionary, an
AUG_SORTED_DICT, is a
sorted dictionary that can also report all of its values combined into one.
Besides the key structure, MkTreapAugDict takes three parameters
that say how values combine:
type value, the type of the values;val combine : value * value -> value, which combines two
values and must be associative;val identity : value, the identity of combine:
combining it with any value x, on either side, gives back
x.
reducedVal d combines all the values of d with
combine, in key order, and returns identity if
d is empty. The dictionary keeps this combined value up to date as it is built, so
reducedVal takes constant time. Since getRange takes
logarithmic time, the two together give the combined value of any range of keys
in logarithmic time, without visiting the values in the range.
The examples below ask different questions of one week of a shop's daily profit, keyed by day. The shop lost money on days 3 and 5:
val week = Seq.fromList [(1, 10), (2, 30), (3, ~25), (4, 30), (5, ~15)] (* (day, profit) *)Total profit.
Addition is a monoid on integers: combine is op+, and
its identity is 0, since adding 0 changes nothing. With
these, reducedVal of a range is the total profit over those days:
structure Totals = MkTreapAugDict (structure Key = IntElt
type value = int
val combine = op+
val identity = 0)
val totals = Totals.fromSeq week
val midweek = Totals.reducedVal (Totals.getRange totals (2, 5)) (* 30 - 25 + 30 = 35 *)
getRange d (lo, hi) includes lo but not
hi, so the range (2, 5) holds days 2, 3 and 4.
The best day. Now suppose we want the most profitable day in a range. That takes two changes.
First, the answer is a day, but reducedVal only combines values; it
never sees the keys. So each value has to carry its own day, as a pair
(day, profit), and combine keeps whichever of its two
pairs has the larger profit.
Second, combine needs an identity: a value that it always discards
in favor of the other argument. That value is also what reducedVal
returns for a range with no days in it, which has no best day. No pair can play
this role, because whatever profit it held, a real day could do no better, and
combine would then keep the identity instead of the day. So the values
are options: SOME (day, profit) for a real day, and
NONE, meaning "no day", as the identity:
(* The better of two days, each SOME (day, profit) or NONE for no day *)
fun better (NONE, b) = b
| better (a, NONE) = a
| better (a as SOME (_, p1), b as SOME (_, p2)) = if p2 > p1 then b else a
structure BestDays = MkTreapAugDict (structure Key = IntElt
type value = (int * int) option
val combine = better
val identity = NONE)
(* Day d's entry: its profit p, together with d itself *)
fun withDay (d, p) = (d, SOME (d, p))
val days = BestDays.fromSeq (Seq.map withDay week)
val best = BestDays.reducedVal days (* SOME (2, 30) *)
val bestLate = BestDays.reducedVal (BestDays.getRange days (3, 6)) (* SOME (4, 30) *)
withDay turns each day's profit into its value,
SOME (day, profit). When two days made the same profit,
better keeps its left argument, which is the earlier day: days 2 and
4 both made 30, and the best day of the week is day 2. Swapping the arguments of
better can therefore change its answer, so it is not commutative.
That is fine, because values are always combined in key order, so
combine only needs to be associative.
The most the shop made over a run of consecutive days is the maximum contiguous subsequence sum (MCSS) of its profits, from MCSSLab. The best run of a range cannot be found from the best runs of its two halves alone, because it might cross the middle: a run ending at the left half's last day followed by a run starting at the right half's first day. So, as in the divide-and-conquer solution, each value summarizes a range of days with four numbers:
total, the range's total profit;prefix, the most made by a run starting at its first day;suffix, the most made by a run ending at its last day;best, the most made by any run.
The last three count the empty run, which makes 0, so they are never negative.
combineRuns combines the summaries of two adjacent ranges, left then
right, and its identity noDays is the summary of no days at all,
which is all zeros:
type summary = {total : int, prefix : int, suffix : int, best : int}
(* The summary of two adjacent ranges, left then right *)
fun combineRuns ({total = t1, prefix = p1, suffix = s1, best = b1},
{total = t2, prefix = p2, suffix = s2, best = b2}) : summary =
{total = t1 + t2,
prefix = Int.max (p1, t1 + p2),
suffix = Int.max (s2, s1 + t2),
best = Int.max (Int.max (b1, b2), s1 + p2)}
(* The summary of no days at all *)
val noDays : summary = {total = 0, prefix = 0, suffix = 0, best = 0}
structure BestRuns = MkTreapAugDict (structure Key = IntElt
type value = summary
val combine = combineRuns
val identity = noDays)
(* Day d's entry: the summary of a range holding just that day *)
fun summarize (d, p) =
let val q = Int.max (p, 0)
in (d, {total = p, prefix = q, suffix = q, best = q}) end
val runs = BestRuns.fromSeq (Seq.map summarize week)
val bestRun = #best (BestRuns.reducedVal runs) (* 45: days 1 to 4 *)
val bestLateRun = #best (BestRuns.reducedVal (BestRuns.getRange runs (3, 6))) (* 30: day 4 *)
reducedVal combines values directly, so each day's value has to be
a summary already: summarize gives each day the summary of a range
holding just that day. The best run of the week makes 45, from day 1 through
day 4, despite the loss on day 3.