<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN">
<HTML>
<HEAD>
<META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=us-ascii">
<META NAME="Generator" CONTENT="MS Exchange Server version 6.5.7232.77">
<TITLE>combining IntMaps</TITLE>
</HEAD>
<BODY>
<!-- Converted from text/rtf format -->

<P><FONT SIZE=2 FACE="Arial">I'm using the (IntMap Int) type to implement functions (Int -&gt; Int), by treating non-keys as values that map to zero. I'd like to be able to add two of these pointwise, and delete the key from the resulting map when the sum of the values is zero. My specification is</FONT></P>

<P><FONT SIZE=2 FACE="Arial">addMaps :: IntMap Int -&gt; IntMap Int -&gt; IntMap Int</FONT>

<BR><FONT SIZE=2 FACE="Arial">addMaps m = IntMap.filter (/= 0) . IntMap.unionWith (+) m</FONT>
</P>

<P><FONT SIZE=2 FACE="Arial">But I'm not really happy with this because it traverses both maps for the union, and then traverses the result to get rid of all the zeros. (This function is a performance bottleneck in my current code).</FONT></P>

<P><FONT SIZE=2 FACE="Arial">I thought I could do something like</FONT>
</P>

<P><FONT SIZE=2 FACE="Arial">addMaps' :: IntMap Int -&gt; IntMap Int -&gt; IntMap Int</FONT>

<BR><FONT SIZE=2 FACE="Arial">addMaps' = IntMap.foldWithKey f</FONT>

<BR><FONT SIZE=2 FACE="Arial">&nbsp;&nbsp;&nbsp; where</FONT>

<BR><FONT SIZE=2 FACE="Arial">&nbsp;&nbsp;&nbsp; f k x = IntMap.update (maybeAdd x) k</FONT>

<BR><FONT SIZE=2 FACE="Arial">&nbsp;&nbsp;&nbsp; maybeAdd x v = let s = v + x in if s == 0 then Nothing else Just s</FONT>
</P>

<P><FONT SIZE=2 FACE="Arial">But this is no good, because IntMap.update only affects those keys where lookup succeeds, so</FONT>

<BR><FONT SIZE=2 FACE="Arial">IntMap.update (maybeAdd 3) 8 IntMap.empty</FONT>

<BR><FONT SIZE=2 FACE="Arial">returns IntMap.empty, rather than a map with 8 -&gt; 3 as I had hoped.</FONT>
</P>

<P><FONT SIZE=2 FACE="Arial">What would you suggest to help addMaps run faster? Do I need to pry open the IntMap implementation to do better?</FONT>
</P>

<P><FONT SIZE=2 FACE="Arial">Thanks so much,</FONT>

<BR><FONT SIZE=2 FACE="Arial">Chad Scherrer</FONT>
</P>

<P><FONT SIZE=2 FACE="Arial">PS - I mistakenly crosslisted this to the GHC users list, because I didn't realize how the mailing lists were set up. Please excuse my noobiness.</FONT></P>

</BODY>
</HTML>