On Tue, Oct 21, 2008 at 3:02 PM, Justin Bailey <[EMAIL PROTECTED]> wrote: > On Tue, Oct 21, 2008 at 11:43 AM, Luke Palmer <[EMAIL PROTECTED]> 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 _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
