Trie
Functional key-value hash maps.
Functional maps (and sets) whose representation is "canonical", and independent of operation history (unlike other popular search trees).
The representation we use here comes from Section 6 of ["Incremental computation via function caching", Pugh & Teitelbaum](https://dl.acm.org/citation.cfm?id=75305).
User’s overview
This module provides an applicative (functional) hash map.
Notably, each put produces a new trie and value being replaced, if any.
Those looking for a more familiar (imperative,
object-oriented) hash map should consider TrieMap or HashMap instead.
The basic Trie operations consist of:
- put - put a key-value into the trie, producing a new version.
- get - get a key’s value from the trie, or null if none.
- iter - visit every key-value in the trie.
The put and get operations work over Key records,
which group the hash of the key with its non-hash key value.
import Trie "mo:base/Trie";
import Text "mo:base/Text";
type Trie<K, V> = Trie.Trie<K, V>;
type Key<K> = Trie.Key<K>;
func key(t: Text) : Key<Text> { { key = t; hash = Text.hash t } };
let t0 : Trie<Text, Nat> = Trie.empty();
let t1 : Trie<Text, Nat> = Trie.put(t0, key "hello", Text.equal, 42).0;
let t2 : Trie<Text, Nat> = Trie.put(t1, key "world", Text.equal, 24).0;
let n : ?Nat = Trie.put(t1, key "hello", Text.equal, 0).1;
assert (n == ?42);AssocList
type AssocList<K, V> = AssocList.AssocList<K, V>Key
type Key<K> = { hash : Hash.Hash; key : K }isValid
func isValid<K, V>(t : Trie<K, V>, enforceNormal : Bool) : BoolChecks the invariants of the trie structure, including the placement of keys at trie paths
empty
func empty<K, V>() : Trie<K, V>An empty trie.
size
func size<K, V>(t : Trie<K, V>) : NatGet the number of key-value pairs in the trie, in constant time. Get size in O(1) time.
merge
Merge tries, preferring the right trie where there are collisions in common keys.
note: the disj operation generalizes this merge
operation in various ways, and does not (in general) lose
information; this operation is a simpler, special case.
disj
Map disjunction.
This operation generalizes the notion of "set union" to finite maps.
Produces a "disjunctive image" of the two tries, where the values of matching keys are combined with the given binary operator.
For unmatched key-value pairs, the operator is still applied to create the value in the image. To accomodate these various situations, the operator accepts optional values, but is never applied to (null, null).
Implements the database idea of an ["outer join"](https://stackoverflow.com/questions/38549/what-is-the-difference-between-inner-join-and-outer-join).
join
Map join.
Implements the database idea of an ["inner join"](https://stackoverflow.com/questions/38549/what-is-the-difference-between-inner-join-and-outer-join).
This operation generalizes the notion of "set intersection" to finite maps. The values of matching keys are combined with the given binary operator, and unmatched key-value pairs are not present in the output.
foldUp
func foldUp<K, V, X>(t : Trie<K, V>, bin : (X, X) -> X, leaf : (K, V) -> X, empty : X) : XThis operation gives a recursor for the internal structure of tries. Many common operations are instantiations of this function, either as clients, or as hand-specialized versions (e.g., see , map, mapFilter, some and all below).
prod
Map product.
Conditional catesian product, where the given
operation op conditionally creates output elements in the
resulting trie.
The keyed structure of the input tries are not relevant for this operation: all pairs are considered, regardless of keys matching or not. Moreover, the resulting trie may use keys that are unrelated to these input keys.
Build
let BuildRepresent the construction of tries as data.
This module provides optimized variants of normal tries, for more efficient join queries.
The central insight is that for (unmaterialized) join query results, we do not need to actually build any resulting trie of the resulting data, but rather, just need a collection of what would be in that trie. Since query results can be large (quadratic in the DB size), avoiding the construction of this trie provides a considerable savings.
To get this savings, we use an ADT for the operations that would build this trie, if evaluated. This structure specializes a rope: a balanced tree representing a sequence. It is only as balanced as the tries from which we generate these build ASTs. They have no intrinsic balance properties of their own.
fold
func fold<K, V, X>(t : Trie<K, V>, f : (K, V, X) -> X, x : X) : XFold over the key-value pairs of the trie, using an accumulator. The key-value pairs have no reliable or meaningful ordering.
some
func some<K, V>(t : Trie<K, V>, f : (K, V) -> Bool) : BoolTest whether a given key-value pair is present, or not.
all
func all<K, V>(t : Trie<K, V>, f : (K, V) -> Bool) : BoolTest whether all key-value pairs have a given property.
toArray
func toArray<K, V, W>(t : Trie<K, V>, f : (K, V) -> W) : [W]Gather the collection of key-value pairs into an array of a (possibly-distinct) type.
isEmpty
func isEmpty<K, V>(t : Trie<K, V>) : BoolTest for "deep emptiness": subtrees that have branching structure, but no leaves. These can result from naive filtering operations; filter uses this function to avoid creating such subtrees.
equalStructure
Test for equality, but naively, based on structure.
Does not attempt to remove "junk" in the tree;
For instance, a "smarter" approach would equate
#bin {left = #empty; right = #empty}
with
#empty.
We do not observe that equality here.