[Haskell-cafe] Re: Grouping - Map / Reduce

Heinrich Apfelmus apfelmus at quantentunnel.de
Thu Mar 26 17:20:33 EDT 2009

Luke Palmer wrote:
> On Tue, Mar 24, 2009 at 3:15 PM, Gü?nther Schmidt <gue.schmidt at web.de>wrote:
>> Hi,
>> let say I got an unordered lazy list of key/value pairs like
>> [('a', 99), ('x', 42), ('a', 33) ... ]
>> and I need to sum up all the values with the same keys.
>> So far I wrote a naive implementation, using Data.Map, foldl and
>> insertWith.
>> The result of this grouping operation, which is effectively another list
>> of key/value pairs, just sums this time, needs to be further processed.
>> The building of this map is of course a bottleneck, the successive
>> processing needs to wait until the entire list is eventually consumed
>> the Map is built and flattened again.
>> Is there another way of doing this, something more "streaming
>> architecture" like?
> Yeah, make a trie.  Here's a quick example.


There was a thread about this question a few years ago, with some very
interesting developments like the "blueprint technique" by Bertram




More information about the Haskell-Cafe mailing list