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 ( foldl'
                 )
import Data.Map  ( Map
                 , empty
                 , insertWith
                 , insertWith'
                 , fromListWith
                 )

-- 1ª definición (por recursión):
frecuencias1 :: Ord a => [a] -> Map a Int
frecuencias1 []     = empty
frecuencias1 (x:xs) = insertWith (+) x 1 (frecuencias1 xs)

-- 2ª definición (por plegado)
frecuencias2 :: Ord a => [a] -> Map a Int
frecuencias2 = foldl' (\d x-> insertWith' (+) x 1 d) empty

-- 3ª definición (con fromList):
frecuencias3 :: Ord a => [a] -> Map a Int
frecuencias3 xs = fromListWith (+) (zip xs (repeat 1))

-- Comparación de eficiencia
--    λ> 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)