On Tue, Mar 24, 2009 at 3:51 PM, Luke Palmer <span dir="ltr">&lt;<a href="mailto:lrpalmer@gmail.com">lrpalmer@gmail.com</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;">
<div class="im">On Tue, Mar 24, 2009 at 3:15 PM, GŁ?nther Schmidt <span dir="ltr">&lt;<a href="mailto:gue.schmidt@web.de" target="_blank">gue.schmidt@web.de</a>&gt;</span> wrote:<br></div><div class="gmail_quote"><div class="im">
<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><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></div>
</div></blockquote><div><br>This definition of singleton unnecessarily leaks memory in some cases.† Here&#39;s a better one:<br><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">singleton ch x = IntTrie $ replicate ch mempty ++ [x] ++ repeat mempty</span><br>
<br>Luke<br><br></div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"><div class="gmail_quote"><div><span style="font-family: courier new,monospace;"></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>
</blockquote></div><br>