Luke Palmer wrote: > On Tue, Mar 24, 2009 at 3:15 PM, Gü?nther Schmidt <gue.schm...@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 _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe