I think it's better to use the longest common prefix approach instead of this one based on individual characters at each level.
Here are some functions for doing essentially constant-time operations on key-value maps in a purely functional style.
A key-value map is an assoc-list which is ordered by the key character at a specific position. The top-level map starts with position 0, and each level of nesting increments the position by 1.
First, here is the map_get function:
\map_get == (\map\pos\key
map
absent
\head\tail
head \top_key\top_node
long_compare (string_at key pos) (string_at top_key pos)
absent
(
top_node \top_val\top_map
string_compare key top_key
absent
(present top_val)
(map_get top_map (long_add pos 1) key)
)
(map_get tail pos key)
)
\map_get = (\map\key map_get map 0 key)
So (map_get map key) returns either absent if the key is missing, or (present value) if the key exists with that value. Oh and the "absent" and "present" functions are defined as follows, using the standard technique for representing "variant records" or "unions" as lamba expressions:
\absent = ( \absent\present absent) \present = (\value \absent\present present value)
If you need a little more guidance with the map_get code, here it is with some comments sprinkled in to highlight the distinct cases it handles:
\map_get == (\map\pos\key
map
# Map is empty, so return absent.
absent
# Map consists of head and tail.
\head\tail
# The head is a pair of top_key and top_node.
head \top_key\top_node
# Now let's compare the characters at the given position. This is a
# three-way comparison.
long_compare (string_at key pos) (string_at top_key pos)
# Key character is less than top key character, so return absent.
absent
# Key character equals the top key character, so let's think some more.
(
# The top_node is a pair of top_val and top_map.
top_node \top_val\top_map
# Compare the key with the top_key. (Three-way comparison)
string_compare key top_key
# Key is less than top key, so it's absent.
absent
# Key equals top key, so return the top value.
(present top_val)
# Key is greater than top key, so look it up in the nested
# map at the next character position.
(map_get top_map (long_add pos 1) key)
)
# Key character is greater than top key character, so look it up
# in the tail of the map.
(map_get tail pos key)
)
\map_get = (\map\key map_get map 0 key)
Now without further ado I present the map_put function:
\map_put == (\map\pos\key\val
map
(item (pair key (pair val end)) map)
\head\tail
head \top_key\top_node
long_compare (string_at key pos) (string_at top_key pos)
(item (pair key (pair val end)) map)
(
top_node \top_val\top_map
\new_head =
(
string_compare key top_key
(
\top_map = (map_put top_map (long_add pos 1) top_key top_val)
pair key (pair val top_map)
)
(pair key (pair val top_map))
(
\top_map = (map_put top_map (long_add pos 1) key val)
pair top_key (pair top_val top_map)
)
)
item new_head tail
)
(
\tail = (map_put tail pos key val)
item head tail
)
)
\map_put = (\map\key\val map_put map 0 key val)
I also have a couple of functions where you give it a key and it returns either the next key after that key or the previous key before it. This allows a "random access" into the key ordering at any given point. I could also easily write a function which simply gave you the list of all keys, either forward or in reverse, but I thought this map_next and map_prev approach was pretty neat so here it is.
Return the lowest key that is strictly greater than the given key, if any.
\map_next == (\map\pos\key
map
absent
\head\tail
head \top_key\top_node
long_compare (string_at key pos) (string_at top_key pos)
(present top_key)
(
top_node \top_val\top_map
string_lt key top_key
(present top_key)
(map_next top_map (long_add pos 1) key
(map_next tail pos key)
present
)
)
(map_next tail pos key)
)
\map_next = (\map\key map_next map 0 key)
Return the highest key that is strictly less than the given key, if any.
\map_prev == (\map\pos\key
map
absent
\head\tail
map_prev tail pos key
(
head \top_key\top_node
top_node \top_val\top_map
long_compare (string_at key pos) (string_at top_key pos)
absent
(
string_le key top_key
absent
(
map_prev top_map (long_add pos 1) key
(present top_key)
present
)
)
(map_prev top_map pos key
(present top_key)
present)
)
present
)
\map_prev = (\map\key map_prev map 0 key)