Add unzip and unzipWith for Map and IntMap

[treeowl]

The these package provides an unzip for these types, but it's a "two pass" fmap-based implementation that can leak memory. I suggested a solution using traverseBia from bifunctors, but that was rejected as too hard to understand. @phadej recommended adding the unzipper to containers instead. We can do this fairly simply, and certainly more efficiently than traverseBia can (at least until ekmett/bifunctors#93 eventually reaches Hackage).

I'll try to implement these next weekend; if someone else gives it a shot, they should be mindful of the fairly subtle NOINLINE tricks that tend to be required to ensure we get the selector thunks we want.

[meooow25]

Why do we need tricks? I would expect a straightforward implementation. Assuming it's something like

unzipWith :: (a -> (b, c)) -> Map k a -> (Map k b, Map k c)

I think it is reasonable to match on the pairs and build up both Maps at once. And we force bs and cs for strict Map and not for lazy Map.

[treeowl]

We might not need a lot of tricks, but GHC's selector thunk trick to prevent memory leaks is a bit fragile under optimization. For lazy maps, we need to make sure that the result maps contain actual selector thunks and not (semantically equivalent) application thunks.

[meooow25]

I don't see why we want selector thunks at all. Here's what I was thinking of:

unzipWith :: (a -> (b, c)) -> Map k a -> (Map k b, Map k c)
unzipWith f t = case go t of t1 :*: t2 -> (t1, t2)
  where
    go Tip = Tip :*: Tip
    go (Bin sz k x l r) = case (go l, f x, go r) of
      (l1 :*: l2, (x1, x2), r1 :*: r2) -> Bin sz k x1 l1 r1 :*: Bin sz k x2 l2 r2

[treeowl]

Sorry, it's been a while since I thought about these things, and I've mixed up requirements with a different context. Yes, your version is good. But it may or may not be useful to have another version, equivalent to the naive fmap-based one but without its memory leaks:

unzipWith_lazy :: (a -> (b, c)) -> Map k a -> (Map k b, Map k c)
unzipWith_lazy f m = (l, r)
  where 
    (l, r) = unzipWith_l f m

unzipWith_l :: (a -> (b, c)) -> Map k a -> (Map k b, Map k c)
-- This is the concept; if we decide to do this we can add the selector thunk tricks
unzipWith_l f t = case go t of t1 :*: t2 -> (t1, t2)
  where
    go Tip = Tip :*: Tip
    go (Bin sz k x l r) = case (go l, f x, go r) of
      -- lazy pattern match
      (l1 :*: l2, ~(x1, x2), r1 :*: r2) -> Bin sz k x1 l1 r1 :*: Bin sz k x2 l2 r2

[meooow25]

I see what you mean, though I don't know of a situation where I would want this version.

Also, it is possible to define this in terms of the other one.

unzipWith_l f = unzipWith (\x -> let (y, z) = f x in (y, z))

[treeowl]

I agree, we want your version. My mind was stuck on what makes sense for arbitrary Traversable containers, which don't offer anything like that.

[meooow25]

@treeowl are you working on this?

[treeowl]

I forgot about it, sorry. I'll try to get to it this week.