[Haskell-cafe] Spine-lazy "multiqueue"

[Luke Palmer]

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:

  dequeue 1 (foldr (enqueue 1) empty [42..]) = Just (42, ...)

  (where dequeue :: k -> QMap k v -> Maybe (v, QMap k v), similarly for enqueue)

I also need a unionWith :: ([v] -> [v] -> [v]) -> QMap k v -> QMap k v
-> QMap k v.

I realize that these might be some pretty tough requirements to meet.
Any pointers or original ideas?

Thanks,
Luke