On 10/21/08, Luke Palmer
Well, first, my question was highly malformed. I actually just want a spine lazy map of lists; queues were not what I wanted. [...] The best I've come up with so far is a binary search tree where the most recently inserted thing is at the root. It's not balanced, because balancing would make it strict (as far as I can tell). So it's only logarithmic time sometimes.
Surely a trie would do the job? With each node a map? One could probably even produce a Patricia trie at some constant cost to keep things on the order of number of elements (ish)rather than on the order of length of elements. Either way its not exactly going to be log (n) but depending on what you're storing it might be as efficient if not more so, and indeed would let you be lazy in the amount of each key consumed (assuming keys are, e.g., lists and not ints) as well as in the spine. --Sterl.