Count number of occurrences of each item in a list

freq.hs

import Control.Arrow ((&&&))
import Control.Monad.State
import Data.List as L
import Data.Map as M
import Data.Ord
import Data.Traversable

type Freq a = [(a,Int)]

freq :: Ord a => [a] -> Freq a
freq = M.toList . L.foldl' (\acc x -> insertWith (+) x 1 acc) M.empty

freq' :: (Ord a, Traversable t) => t a -> Freq a
freq' = 
    let updateState a = modify (insertWith (+) a 1)
        run = flip execState M.empty
    in M.toList . run . traverse updateState

-- from @mwotton:
freq'' :: Ord a => [a] -> Freq a
freq'' = map (head &&& length) . group . sort