frecuencias :: Ord a => [a] -> Map a Int

λ> frecuencias "sosos"
fromList [('o',2),('s',3)]
λ> frecuencias (show (10^100))
fromList [('0',100),('1',1)]
λ> frecuencias (take (10^6) (cycle "abc"))
fromList [('a',333334),('b',333333),('c',333333)]
λ> size (frecuencias (take (10^6) (cycle [1..10^6])))
1000000

import Data.List as L
import Data.Map
import Test.QuickCheck

-- 1ª solución
-- ===========

frecuencias1 :: Ord a => [a] -> Map a Int
frecuencias1 []     = empty
frecuencias1 (x:xs) = insertWith (+) x 1 (frecuencias1 xs)

-- 2ª solución
-- ===========

frecuencias2 :: Ord a => [a] -> Map a Int
frecuencias2 = L.foldl' (\d x-> insertWith' (+) x 1 d) empty

-- 3ª solución
-- ===========

frecuencias3 :: Ord a => [a] -> Map a Int
frecuencias3 xs = fromListWith (+) (zip xs (repeat 1))

-- Equivalencia de las definiciones
-- ================================

-- La propiedad es
prop_frecuencias_equiv :: [Int] -> Bool
prop_frecuencias_equiv xs =
  all (== frecuencias1 xs) [ frecuencias2 xs
                           , frecuencias3 xs]

-- La comprobación es
--    λ> quickCheck prop_frecuencias_equiv
--    +++ OK, passed 100 tests.

-- Comparación de eficiencia
-- =========================

-- La comparación es
--    λ> frecuencias1 (take (10^6) (cycle "abc"))
--    fromList [('a',333334),('b',333333),('c',333333)]
--    (3.85 secs, 479811608 bytes)
--    λ> frecuencias2 (take (10^6) (cycle "abc"))
--    fromList [('a',333334),('b',333333),('c',333333)]
--    (0.72 secs, 218612192 bytes)
--    λ> frecuencias3 (take (10^6) (cycle "abc"))
--    fromList [('a',333334),('b',333333),('c',333333)]
--    (1.02 secs, 316011224 bytes)

--    λ> size (frecuencias1 (take (10^6) (cycle [1..10^6])))
--    1000000
--    (11.35 secs, 2435622280 bytes)
--    λ> size (frecuencias2 (take (10^6) (cycle [1..10^6])))
--    1000000
--    (2.83 secs, 1621887768 bytes)
--    λ> size (frecuencias3 (take (10^6) (cycle [1..10^6])))
--    1000000
--    (2.77 secs, 1637299328 bytes)