[Haskell-cafe] Grouping - Map / Reduce

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

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.

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

More information about the Haskell-Cafe mailing list