CODEWITHSUNDEEP
haskellcountcounting
user3496846
user3496846

Reputation: 1665

Count all occurences of each element in a list

How do I efficiently count all occurences of each element in a list? I thought of using an associative list or some hash map, but immutability gets in the way and it's not evidently clear how an (hopefully) elegant solution should arise.

The signature could be like this:

countOccurences :: [a] -> [(a, Int)]

Example:

countOccurences [1, 1, 2, 3, 1, 2, 4]

results in 

[(1, 3), (2, 2), (3, 1), (4, 1)]

(order is not important though).

Upvotes: 3

Views: 1012

Answers (2)

sshine
sshine

Reputation: 16145

Since chi provided a solution using group . sort, here is one that uses Data.Map:

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

histogram :: Ord a => [a] -> Map a Int
histogram = M.fromListWith (+) . (`zip` [1,1..])

This also uses O(n log n) time.

I thought of using an associative list or some hash map, but immutability gets in the way

Data.Map is a tree-based associative map, so maybe this representation is for you.

If you'd rather like an [(a, Int)], M.assocs can convert the Data.Map back:

countOccurrences :: Ord a => [a] -> [(a, Int)]
countOccurrences = M.assocs . histogram

Upvotes: 6

chi
chi

Reputation: 116174

group . sort will produce an output list such as

> group . sort $ [1, 1, 2, 3, 1, 2, 4] 
[[1,1,1],[2,2],[3],[4]]

Hence,

> map (head &&& length) . group . sort $ [1, 1, 2, 3, 1, 2, 4] 
[(1,3),(2,2),(3,1),(4,1)]

So, we obtain

import Data.List (group, sort)
import Control.Arrow ((&&&))

countOccurences :: Ord a => [a] -> [(a, Int)]
countOccurences = map (head &&& length) . group . sort

It should require only O(n log n) time.

Upvotes: 8

Related Questions