On Tue, Mar 24, 2009 at 3:15 PM, Gü?nther Schmidt <span dir="ltr">&lt;<a href="mailto:gue.schmidt@web.de">gue.schmidt@web.de</a>&gt;</span> wrote:<br><div class="gmail_quote"><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
Hi,<br>
<br>
let say I got an unordered lazy list of key/value pairs like<br>
<br>
[(&#39;a&#39;, 99), (&#39;x&#39;, 42), (&#39;a&#39;, 33) ... ]<br>
<br>
and I need to sum up all the values with the same keys.<br>
<br>
So far I wrote a naive implementation, using Data.Map, foldl and insertWith.<br>
<br>
The result of this grouping operation, which is effectively another list<br>
of key/value pairs, just sums this time, needs to be further processed.<br>
<br>
The building of this map is of course a bottleneck, the successive<br>
processing needs to wait until the entire list is eventually consumed<br>
the Map is built and flattened again.<br>
<br>
Is there another way of doing this, something more &quot;streaming<br>
architecture&quot; like?</blockquote><div><br>Yeah, make a trie.  Here&#39;s a quick example.<br><br><span style="font-family: courier new,monospace;">import Data.Monoid</span><br style="font-family: courier new,monospace;">
<br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">newtype IntTrie a = IntTrie [a]</span><br style="font-family: courier new,monospace;"><br style="font-family: courier new,monospace;">
<span style="font-family: courier new,monospace;">singleton :: (Monoid a) =&gt; Int -&gt; a -&gt; IntTrie a</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">singleton ch x = IntTrie [ if fromIntegral ch == i then x else mempty | i &lt;- [0..] ]</span><br style="font-family: courier new,monospace;">
<br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">lookupTrie :: IntTrie a -&gt; Int -&gt; a</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">lookupTrie (IntTrie xs) n = xs !! n</span><br style="font-family: courier new,monospace;">
<br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">instance (Monoid a) =&gt; Monoid (IntTrie a) where</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">    mempty = IntTrie (repeat mempty)</span><br style="font-family: courier new,monospace;">
<span style="font-family: courier new,monospace;">    mappend (IntTrie xs) (IntTrie ys) = IntTrie (infZipWith mappend xs ys)</span><br style="font-family: courier new,monospace;"><br style="font-family: courier new,monospace;">
<span style="font-family: courier new,monospace;">infZipWith f ~(x:xs) ~(y:ys) = f x y : infZipWith f xs ys</span><br style="font-family: courier new,monospace;"><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">test = mconcat [ singleton (n `mod` 42) [n] | n &lt;- [0..] ] `lookupTrie` 10</span><br style="font-family: courier new,monospace;">
<br>This is an inefficient way to find the class of n such that n mod 42 = 10.  Note that it works on an infinite list of inputs.<br><br>Here the &quot;trie&quot; was a simple list, but you could replace it with a more advanced data structure for better performace.<br>
<br>Luke<br></div></div><br>