Re: [Haskell-cafe] Efficient functional idiom for histogram

2009/7/31 Gregory Collins :

Paul Moore writes:

...

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

   import qualified Data.Map as Map    import           Data.Map (Map)

   histogram :: Ord a => [a] -> [(a,Int)]    histogram = Map.assocs . foldl f Map.empty      where        f m k = Map.insertWith (+) k 1 m

Right. I see how that works, and can work out how to think about this sort of thing from your example. Thanks very much. BTW, I did know that Haskell had an efficient map implementation, I just wasn't sure how to use it "functionally" - I probably should have searched a bit harder for examples before posting. Thanks for the help in any case. Paul.