The type of tries. 'a list is the type of keys, 'b the type of values. Internally, a trie is represented as a labeled tree, where node contains values of type 'a * 'b option.

Creates an empty trie.

mem t k returns true if a value is associated with the key k in the trie t. Otherwise, it returns false.

find t k returns the value associated with the key k in the trie t. Returns Not_found if no values are associated with k in t.

set t k v associates the value v with the key k in the trie t.

unset k v removes the association of value v with the key k in the trie t. Moreover, it automatically clean the trie, ie. it removes recursively every nodes of t containing no values and having no chil.

iter f t applies the function f to every node of the trie t. As nodes of the trie t do not necessary contains a value, the second argument of f is an option type.

iter_path f t p iterates f over nodes associated with the path p in the trie t. If p is not a valid path of t, it iterates on the longest valid prefix of p.

fold f t x fold f over every nodes of t, with x as initial value.

map f t maps f over every values stored in t. The return value of f is of type 'c option as one may wants to remove value associated to a key. This function is not tail-recursive.

sub t p returns the sub-trie associated with the path p in the trie t. If p is not a valid path of t, it returns an empty trie.