[Haskell-cafe] Grouping - Map / Reduce
ketil at malde.org
Tue Mar 24 19:26:15 EDT 2009
"Gü?nther Schmidt" <gue.schmidt at web.de> writes:
> 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 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.
Sure this is not an artifact of the laziness of foldl?
> Is there another way of doing this, something more "streaming
> architecture" like?
I don't see how you can do this much better - for a small, fixed set
of keys, you could use an (STU) array for the sums, but it depends if
the added complexity is worth it. You're already doing a single pass
over the data.
If I haven't seen further, it is by standing in the footprints of giants
More information about the Haskell-Cafe