[Haskell-cafe] Efficient functional idiom for histogram

Paul Moore p.f.moore at gmail.com
Fri Jul 31 16:39:53 EDT 2009


How would I efficiently write a function in Haskell to count
occurrences of unique elements in a (potentially very large) list? For
example, given the list [1,2,3,4,5,3,4,2,4] I would like the output
[[1,1], [2,2], [3,2], [4,3], [5,1]] (or some equivalent
representation).

Clearly, this won't be possible for infinite input, but I would like
it to be as efficient as possible for (lazy) input lists containing
many millions of elements. So an implementation based on group . sort
is not going to work.

In an imperative language like Python, I'd use a dictionary as an
accumulator - something like

    for el in input:
        accums[i] = accums.get(i, 0) + 1

That's about as efficient as you can hope for (assuming an efficient
dictionary implementation). How would I code something equivalent in
Haskell?

Thanks,
Paul.


More information about the Haskell-Cafe mailing list