Diccionario de frecuencias
Definir la función
|
1 |
frecuencias :: Ord a => [a] -> Map a Int |
tal que (frecuencias xs) es el diccionario formado por los elementos de xs junto con el número de veces que aparecen en xs. Por ejemplo,
|
1 2 3 4 5 6 7 8 |
λ> 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 |
Soluciones
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
import Data.List (foldl') import Data.Map (Map, empty, insertWith, fromList, fromListWith, size) 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 = 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 :: [Int] -> Bool prop_frecuencias xs = all (== frecuencias1 xs) [ frecuencias2 xs , frecuencias3 xs] -- La comprobación es -- λ> quickCheck prop_frecuencias -- +++ 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)] -- (0.89 secs, 453,842,448 bytes) -- λ> frecuencias2 (take (10^6) (cycle "abc")) -- fromList [('a',333334),('b',333333),('c',333333)] -- (0.54 secs, 274,181,128 bytes) -- λ> frecuencias3 (take (10^6) (cycle "abc")) -- fromList [('a',333334),('b',333333),('c',333333)] -- (0.29 secs, 313,787,976 bytes) -- λ> size (frecuencias1 (take (10^6) (cycle [1..10^6]))) -- 1000000 -- (3.76 secs, 2,651,926,024 bytes) -- λ> size (frecuencias2 (take (10^6) (cycle [1..10^6]))) -- 1000000 -- (1.03 secs, 1,640,678,448 bytes) -- λ> size (frecuencias3 (take (10^6) (cycle [1..10^6]))) -- 1000000 -- (0.88 secs, 1,672,678,536 bytes) |
El código se encuentra en GitHub.