[Haskell-cafe] Spine-lazy "multiqueue"
s.clover at gmail.com
Tue Oct 21 20:42:21 EDT 2008
On 10/21/08, Luke Palmer <lrpalmer at gmail.com> wrote:
> 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.
More information about the Haskell-Cafe