Claude Heiland-Allen wrote:
On 31/07/10 12:13, wren ng thornton wrote:
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.)
Why not something like this (with the correctness proof as an exercise):
\begin{code}
import Data.Map (Map) import qualified Data.Map as M
unzipMap :: Map a (b, c) -> (Map a b, Map a c) unzipMap m = let (ab, ac) = unzip . map fiddle . M.toAscList $ m in (M.fromDistinctAscList ab, M.fromDistinctAscList ac) where fiddle :: (x, (y, z)) -> ((x, y), (x, z)) fiddle (x, (y, z)) = ((x, y), (x, z))
\end{code}
That O(n)+O(n) is much better than the O(n)*2*O(log n) foldrWithKey/insert version. But it's still about the same as the original 2*O(n) map fst/map snd version. With the primitive I mentioned we could reduce the constant factor by about half. -- Live well, ~wren