Theory LR_Trie
theory LR_Trie
imports LR_Int
begin
section ‹Tables as binary tries›
text ‹A table from naturals to values as a binary trie: the path to a key is
the sequence of bits of its binary numeral, least significant first. With
binary naturals (▩‹Code_Binary_Nat›) a lookup follows the constructors of
the numeral and involves no arithmetic, and a trie is static data.
The datatype is the binary trie of Verbatim++
\<^cite>‹‹Sects.~5.1--5.2› in "egolf2022-verbatim-plus-plus"›, where a memo is keyed by the
length of a suffix as a binary number and a lookup reads the key bit by bit, comparing no
keys. Okasaki and Gill \<^cite>‹"okasaki1998-integer-maps"› treat integer maps as binary
tries (Patricia trees); the trie here is a plain one, with one node per bit of the key.›