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

[Heinrich Apfelmus]

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.

Nice!

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

  http://thread.gmane.org/gmane.comp.lang.haskell.cafe/15135


Regards,
apfelmus

--
http://apfelmus.nfshost.com