[Haskell-cafe] Spine-lazy "multiqueue"

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