search

glguy / tries

BSD 3-Clause "New" or "Revised" License
11 stars 8 forks source link

Nested insertion is bad #23

Closed treeowl closed 2 years ago

treeowl commented 2 years ago

Currently, inserting into the trie of a product type will perform a (nested) lookup followed by a (nested) insertion. We can avoid this by adding a method that inserts or modifies a value. Something vaguely like

insMod :: (Maybe v -> Solo v) -> GTrie k v -> GTrie k v

Now insertion into a product trie can use insMod on the outer trie and insert on the inner one (if present).

Another option would be to add alter, which might be a good idea anyway, but for balanced tree types insMod can sometimes be more efficient.

treeowl commented 2 years ago

I'm leaning towards alter, which would also improve the similarly bad situation for deletion.