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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
