[Haskell-cafe] Spine-lazy "multiqueue"

[Luke Palmer]

On Tue, Oct 21, 2008 at 3:02 PM, Justin Bailey <jgbailey at gmail.com> wrote:
> On Tue, Oct 21, 2008 at 11:43 AM, Luke Palmer <lrpalmer at gmail.com> wrote:
>> Hi, I need a rather strange data structure, and I can't find any
>> existing implementations or think of a way to implement it.  It's a
>> "multiqueue", basically a map of queues.  The trick is that it should
>> be lazy in its spine and still support efficient access.  For example,
>> the following should hold:
>>
>
> This doesn't answer your question, but how is a Map of queues not
> "spine-lazy"? I'm mostly looking to understand that term.

Well, first, my question was highly malformed.  I actually just want a
spine lazy map of lists; queues were not what I wanted.

Data.Map is strict in its keys, meaning rougly that you cannot store
infinitely many keys in a map.  So:

  foldr (\x x -> Map.insert x x) Map.empty [0..]  =  _|_

I.e. if you take this map that maps every natural to itself and try to
do anything with it, you will get an infinite loop (or stack overflow,
or whatever).

On the other hand, the "map" type [(k,v)] *is* spine lazy, because, for example:

  lookup 42 [ (x,x) | x <- [0..] ]  = Just 42

It's just not very efficient.  I'm basically looking for a version of
the above which has a logarithmic lookup time.

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.

Luke