Stephen Tetley wrote:
wren ng thornton wrote:
Ben wrote:
unzipMap :: M.Map a (b, c) -> (M.Map a b, M.Map a c)
unzipMap m = (M.map fst m, M.map snd m)
I don't think you can give a more efficient implementation using the public
interface of Data.Map. You need to have a sort of mapping function that
allows you to thread them together, either via continuations or via a
primitive:
Unless I'm missing something. This one has one traversal...
unzipMap :: Ord a => M.Map a (b, c) -> (M.Map a b, M.Map a c)
unzipMap = M.foldrWithKey fn (M.empty,M.empty)
where
fn k a (m1,m2) = (M.insert k (fst a) m1, M.insert k (snd a) m2)
Well, that's one traversal of the original map, but you have to traverse
the new maps repeatedly with all those M.insert calls. And since
Data.Map is a balanced tree, that could lead to a whole lot of work
rebalancing things.
However, because we are not altering the set of keys, we are guaranteed
that the structure of both new maps will be identical to the structure
of the old map. Therefore, with the right primitives, we can keep one
finger in each of the three maps and traverse them all in parallel
without re-traversing any part of the spine. (The Either and Or variants
will have some retraversal as the smart constructors prune out the spine
leading to deleted keys. But this is, arguably, necessary.)
--
Live well,
~wren
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
