[Haskell-cafe] Efficient functional idiom for histogram

Malcolm Wallace malcolm.wallace at cs.york.ac.uk
Sat Aug 1 14:14:51 EDT 2009

> I'm expecting the answer to be that I've got unnecessary laziness -  
> which
> is fine, but ultimately my interest is in ease of expression and
> performance combined, so I'm looking for beginner-level improvements
> rather than subtle advanced techniques like unboxing.

You're right, it is too lazy.  Here are a couple of strictifications  
that should help:

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

Turn foldl into foldl' (from Data.List) and Map.insertWith into  
The strict versions simply force the intermediate structures to be  
evaluated, rather than hanging around as large accumulations of  


More information about the Haskell-Cafe mailing list