<html>
<head>
<meta content="text/html; charset=UTF-8" http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
On 01/26/2012 12:08 AM, Jan-Willem Maessen wrote:
<blockquote
cite="mid:CANs0n6zYULZF_-h=oiO6UEyiOwaLdv_S34WWKeSUCqA8_KbKCA@mail.gmail.com"
type="cite"><br>
<br>
<div class="gmail_quote">On Wed, Jan 25, 2012 at 7:01 PM,
Christian Sattler <span dir="ltr"><<a moz-do-not-send="true"
href="mailto:sattler.christian@gmail.com">sattler.christian@gmail.com</a>></span>
wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0
.8ex;border-left:1px #ccc solid;padding-left:1ex">
<div bgcolor="#FFFFFF" text="#000000">
<div>
<div class="h5">
<blockquote type="cite">
<div class="gmail_quote">
<div>... </div>
<div>As others (including Milan) observed, this
isn't asymptotically efficient if the maps don't
overlap much. Better is the following <span
style="border-collapse:collapse;color:rgb(34,34,34);font-family:arial,sans-serif;font-size:10px">swiss
army knife of combining functions:</span></div>
<span
style="border-collapse:collapse;color:rgb(34,34,34);font-family:arial,sans-serif;font-size:10px">
<div><br>
</div>
<div>combine :: Ord k => (k -> a -> b
-> Maybe c) -- Combine common entries</div>
<div> -> (Map k a
-> Map k c) -- Convert left submap with
no common entries</div>
<div> -> (Map k b
-> Map k c) -- Convert right submap with
no common entries</div>
<div style="color:rgb(80,0,80)">
<div> -> Map k a
-> Map k b -> Map k c</div>
<div><br>
</div>
</div>
<div>Now</div>
<div><br>
</div>
<div> unionWithKey f = combine (\k a b -> Just
(f k a b)) id id</div>
<div> intersectionWithKey f = combine f (const
empty) (const empty)</div>
<div><br>
</div>
<div>with no change in asymptotic complexity, and
a bunch of fusion laws with fmap hold. This
also permits difference and symmetric difference
to be easily defined:</div>
<div><br>
</div>
<div> difference = combine (\_ _ _-> Nothing)
id (const empty)</div>
<div> symmDifference = combine (\_ _ _ ->
Nothing) id id</div>
</span>
<div><br>
</div>
<div>When you inline combine and (where necessary)
mapWithKey, you get exactly the code you'd expect
without fancy footwork to delete the identity tree
traversals.</div>
<div><br>
</div>
<div>-Jan</div>
</div>
</blockquote>
<br>
</div>
</div>
I don't think this solves the complexity issue e.g. for
symmetric difference of a large set of size n^2 with a small
set of size n.<br>
</div>
</blockquote>
<div><br>
</div>
<div>Er, could you be more specific? What case is not handled
that prevents us from matching the asymptotic complexity of a
hand-written symmetric difference function? There should be
O(n) tree splits and joins in either case.</div>
<div><br>
</div>
<div>-Jan</div>
</div>
</blockquote>
<br>
Ah, yes, you are right. Mistake on my part. +1 for the proposal
</body>
</html>