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

2009/7/31 Paul Moore :

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.

Hmm, I'm obviously still mucking up the performance somehow. My full program (still a toy, but a step on the way to what I'm aiming at) is as follows. It's rolling 3 6-sided dice 100000 times, and printing a summary of the results. import System.Random import qualified Data.Map as Map import Data.Map (Map) import Data.List dice :: Int -> Int -> IO Int dice 0 n = return 0 dice m n = do total <- dice (m - 1) n roll <- randomRIO (1, n) return (total + roll) simulate count m n = do mapM (dice m) (replicate count n) histogram :: Ord a => [a] -> [(a,Int)] histogram = Map.assocs . foldl f Map.empty where f m k = Map.insertWith (+) k 1 m simulation = do lst <- simulate 100000 3 6 return (histogram lst) main = do s <- simulation putStrLn (show s) When compiled, this takes over twice as long as a naively implemented Python program. What am I doing wrong here? I'd have expected compiled Haskell to be faster than interpreted Python, so obviously my approach is wrong. 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. Thanks, Paul. PS I know my code is probably fairly clumsy - I'd appreciate style suggestions, but my main interest here is whether a beginner, with a broad programming background, a basic understanding of Haskell, and access to Google, put together a clear, efficient, program (ie, the case where my usual scripting language is too slow and I want to knock something up quickly in a high-level, high-performance language).