Menu Close

Diccionario de frecuencias

Definir la función

   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,

   λ> 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

 
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)

5 soluciones de “Diccionario de frecuencias

  1. fercarnav
    import Data.List as L
    import Data.Map as M
     
    frecuencias :: Ord a => [a] -> Map a Int
    frecuencias xs = frecuencias2 xs (M.empty)
     
    frecuencias2 :: Ord a => [a]-> Map a Int -> Map a Int
    frecuencias2 [] d = d
    frecuencias2 (x:xs) d
      | member x d == True = frecuencias2 xs (M.insertWith (+) x 1 d)
      | otherwise          = frecuencias2 xs (M.insert x 1 d)
  2. Enrique Zubiría
    import Data.Map as M
    import Data.Maybe
     
    frecuencias :: Ord a => [a] -> Map a Int
    frecuencias xs = frecuencias' xs empty
     
    frecuencias' :: Ord a => [a] -> Map a Int -> Map a Int
    frecuencias' [] d = d
    frecuencias' (x:[]) d = cuenta x d
    frecuencias' (x:xs) d = cuenta x (frecuencias' xs d)
     
    cuenta :: Ord a => a -> Map a Int -> Map a Int
    cuenta x d
      | isNothing v   = M.insert x 1 d
      | otherwise     = M.insert x ((fromJust v)+1) d
      where v = M.lookup x d
  3. rebgongor
    import Data.Map
     
    frecuencias :: Ord a => [a] -> Map a Int
    frecuencias []     = empty
    frecuencias (x:xs) = insertWith (+) x 1 $ frecuencias xs
  4. jaicarrod1
    import Data.Map as M
     
    frecuencias :: Ord a => [a] -> Map a Int
    frecuencias xs = fromList [(a,numeroDeVeces a xs)| a <- xs]
     
    numeroDeVeces x [] = 0
    numeroDeVeces y (x:xs) | y == x    = 1 + numeroDeVeces y xs
                           | otherwise = numeroDeVeces y xs
  5. javjimord
    import Data.Map as M
    import Data.List as L
     
    frecuencias :: Ord a => [a] -> Map a Int
    frecuencias xs = M.fromList (zip (nub $ sort xs) (L.map length $ group $ sort xs))

Leave a Reply

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.