[Haskell-cafe] dear traversable

[wren ng thornton]

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