[Haskell-cafe] Suspected stupid Haskell Question

[Yitzchak Gale]

Peter Verswyvelen wrote:
> However, I suspect the experts here will be able to make that much
> shorter and more efficient (maybe using Data.Map?)

That makes it difficult to respond. I am definitely not
claiming to be an expert. For one thing, my name
is not Simon. But I'll say something anyway, fwiw.

The problem there is that nub is O(n^2).
You're stuck with that if your type is not an
instance of Ord (but then you can't use sort,
either).

When you can assume Ord, the standard solution
is, as you suggest, something like:

import qualified Data.Map as M
import Data.List

histogram = M.toList . foldl' (\m x -> M.insertWith' (+) x 1 m)
M.empty . M.fromList

This should work efficiently, with the right amount of laziness, even
for very large lists.

Regards,
Yitz