[Haskell-cafe] Spine-lazy "multiqueue"

[Sterling Clover]

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.

--Sterl.