The type of hierarchical names. The name x.y.z is represented by the OCaml list ["x"; "y"; "z"].

The abstract type of a trie.

The empty trie.

Check whether the trie is empty.

root d makes a trie with the only binding: the root and its associated value d. It is equivalent to root_opt(Some d).

root_opt d is equivalent to match d with None ->empty| Some d ->rootd. In other words, root_opt None will make an empty trie and root_opt (Some v) will make a trie with only one binding: the root associated with the value v. If the input is always Some v, use root.

prefix p t makes a minimum trie with t rooted at p.

singleton (p, d) makes a trie with the only binding: p and its associated value d. It is equivalent to prefixp @@rootd

equal eq t1 t2 checks whether two tries are equal.

find_subtree p t returns the subtree rooted at p.

• returns

  The subtrie with all the bindings under p, including the binding at p itself (which will be the root). If there are no such bindings with the prefix p, an empty trie is returned.

find_singleton p t returns the value at p.

find_root t returns the value at the root. This is equivalent to find_singleton[] t.

iteri ~rev_prefix f t applies the function f to each value v in the trie.

• parameter rev_prefix

  The prefix prepended to any path sent to f, but in reverse. The default is the empty unit path ([]).

mapi ~rev_prefix f t applies the function f to each value v in the trie.

• parameter rev_prefix

  The prefix prepended to any path sent to f, but in reverse. The default is the empty unit path ([]).

filteri ~rev_prefix f t removes all values v at path p such that f ~rev_prefix:p v returns false.

• parameter rev_prefix

  The prefix prepended to any path sent to f. The default is the empty unit path ([]).

filter_mapi ~rev_prefix f t applies the function f to each value v at p in the trie. If f ~rev_prefix:p v returns None, then the binding will be removed from the trie. Otherwise, if f v returns Some v', then the value will be replaced by v'.

• parameter rev_prefix

  The prefix prepended to any path sent to f, but in reverse. The default is the empty unit path ([]).

update_subtree p f t replaces the subtree t' rooted at p in t with f t'.

update_singleton p f t replaces the value v at p in t with the result of f. If there was no binding at p, f None is evaluated. Otherwise, f (Some v) is used. If the result is None, the old binding at p (if any) is removed. Otherwise, if the result is Some v', the value at p is replaced by v'.

update_root f t updates the value at root with f. It is equivalent to update_singleton[] f t.

union ~rev_prefix merger t1 t2 merges two tries t1 and t2. If both tries have a binding at the same path p, it will call merger ~rev_path:p x y to reconcile the values x from t1 and y from t2 that are both bound at the (reversed) path rev_path. The path rev_path is reversed for efficient traversal.

• parameter rev_prefix

  The prefix prepended to any path sent to merger. The default is the empty unit path ([]).

union_subtree ~rev_prefix merger t1 (path, t2) is equivalent to union~rev_prefix merger t1 (prefix path t2), but potentially more efficient.

• parameter rev_prefix

  The prefix prepended to any path sent to merger. The default is the empty unit path ([]).

union_singleton merger t binding is equivalent to unionmerger t1 (singleton binding), but potentially more efficient.

• parameter rev_prefix

  The prefix prepended to any path sent to merger. The default is the empty unit path ([]).

detach_subtree p t detaches the subtree at p from the main trie and returns both the subtree and the remaining trie (in that order). If detach p t returns t1, t2, then union_subtreem t2 (p, t1) should be equivalent to t.

detach_singleton p t detaches the binding at p from the main trie and returns both the binding and the remaining trie. If detach p t returns b, t', then union_subtreem t' (p,root_optb) should be equivalent to t.

to_seq ~rev_prefix t traverses through the trie t in the lexicographical order.

• parameter rev_prefix

  The prefix prepended to any path in the output, but in reverse. The default is the empty unit path ([]).

to_seq_with_reversed_paths is like to_seq but with paths reversed. This is potentially more efficient than to_seq.

• parameter rev_prefix

  The prefix prepended to any path in the output, but in reverse. The default is the empty unit path ([]).

to_seq_values t traverses through the trie t in the lexicographical order but only returns the associated values. This is potentially more efficient than to_seq because path reversal is skipped.

of_seq ~rev_prefix merger s inserts bindings (p, d) into an empty trie, one by one, using union_singleton.

• parameter rev_prefix

  The prefix prepended to any path sent to merger, but in reverse. The default is the empty unit path ([]). Note that rev_prefix does not directly affect the output trie, only the argument to merger.