Counting things

Posted on January 21, 2012

Yet another nice Haskell example: counting stuff. At work last week, a colleague had to count stuff in a list. The task was simply to find out how many times each element occurs in the list. He was unfortunately forced to using XSLT to do so, and his curses could be heard in the next building. He asked me for a way to do this in Haskell, and the answer was, again, short and easy:

import Data.Map

count :: Ord a => [a] -> Map a Int
count = fromListWith (+) . flip zip (repeat 1)

Neglecting the import and type declaration, it is again a one-liner that can count everything that has an order defined (i.e. is in the Ord type class). The run-time is O(n*log(n)).

If there is only an equality test available, the run-time is worse, but it is still a very short function:

import qualified Data.List as L

count2 :: Eq a => [a] -> [(a,Int)]
count2 [] = []
count2 (a:as) = (a,n + 1) : count2 bs
  where (as',bs) = L.partition (==a) as
        n = length as'

Again, Haskell rocks.