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
= fromListWith (+) . flip zip (repeat 1) count
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 [] :as) = (a,n + 1) : count2 bs
count2 (awhere (as',bs) = L.partition (==a) as
= length as' n
Again, Haskell rocks.