Trie — Functional map

List (type)

type List<T> = List.List<T>;public type AssocList<K,V> = AssocList.AssocList<K,V>;

Key (type)

type Key<K> = {  /* `hash` permits fast inequality checks, and permits collisions */
  hash: Hash.Hash;
  /* `key` permits percise equality checks, but only used after equal hashes. */
  key: K;
};

Leaf (type)

type Leaf<K,V> = {  count   : Nat ;
  keyvals : AssocList<Key<K>,V> ;
};

Branch (type)

type Branch<K,V> = {  count : Nat ;
  left  : Trie<K,V> ;
  right : Trie<K,V> ;
};

Trie (type)

type Trie<K,V> = {  #empty  ;
  #leaf   : Leaf<K,V> ;
  #branch : Branch<K,V> ;
};

Trie2D (type)

type Trie2D<K1, K2, V> = Trie<K1, Trie<K2,V> >;

Trie3D (type)

type Trie3D<K1, K2, K3, V> = Trie<K1, Trie2D<K2, K3, V> >;

TrieBuild (type)

type TrieBuild<K,V> = {  #skip ;
  #insert : (K, ?Hash.Hash, V) ;
  #seq : {
    count : Nat ;
    left  : TrieBuild<K,V> ;
    right : TrieBuild<K,V> ;
  } ;
};