[Haskell-cafe] Grouping - Map / Reduce

[Ketil Malde]

"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.

Data.Map.fromListWith (+)

> 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.

-k
-- 
If I haven't seen further, it is by standing in the footprints of giants