Definir la funci\u00f3n<\/p>\n
\n ocurrenciasElementos :: Ord a => [a] -> [(a,Int)]\n<\/pre>\ntal que (ocurrencias xs) es el conjunto de los elementos de xs junto con sus n\u00fameros de ocurrencias. Por ejemplo,<\/p>\n
\n ocurrenciasElementos1 [3,2,3,1,2,3,5,3] == [(3,4),(2,2),(1,1),(5,1)]\n ocurrenciasElementos1 \"tictac\" == [('t',2),('i',1),('c',2),('a',1)]\n<\/pre>\nSoluciones<\/h4>\n\nimport Data.List (group, nub, sort)\nimport Data.Maybe (fromJust)\nimport qualified Data.Map as M\nimport Test.QuickCheck\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nocurrenciasElementos1 :: Ord a => [a] -> [(a,Int)]\nocurrenciasElementos1 xs =\n [(x,ocurrencias x xs) | x <- nub xs]\n\n-- (ocurrencias x xs) es el n\u00famero de ocurrencias de x en xs. Por\n-- ejemplo,\n-- ocurrencias 'a' \"Salamanca\" == 4\nocurrencias :: Ord a => a -> [a] -> Int\nocurrencias x xs = length (filter (==x) xs)\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nocurrenciasElementos2 :: Ord a => [a] -> [(a,Int)]\nocurrenciasElementos2 xs = map ocurrencias (nub xs)\n where ocurrencias x = (x,fromJust (lookup x (frecuencias xs)))\n\n-- (frecuencias xs) es la lista ordenada de los elementos de xs juntos\n-- con sus n\u00fameros de ocurrencias. Por ejemplo,\n-- frecuencias [3,2,3,1,2,3,5,3] == [(1,1),(2,2),(3,4),(5,1)]\nfrecuencias :: Ord a => [a] -> [(a, Int)]\nfrecuencias xs = [(head ys, length ys) | ys <- group (sort xs)]\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nocurrenciasElementos3 :: Ord a => [a] -> [(a,Int)]\nocurrenciasElementos3 xs = map ocurrencias (nub xs)\n where diccionario = dicFrecuencias xs\n ocurrencias x = (x, diccionario M.! x)\n\n-- (dicFrecuencias xs) es el diccionario de los elementos de xs juntos\n-- con sus n\u00fameros de ocurrencias. Por ejemplo,\n-- \u03bb> dicFrecuencias [3,2,3,1,2,3,5,3]\n-- fromList [(1,1),(2,2),(3,4),(5,1)]\ndicFrecuencias :: Ord a => [a] -> M.Map a Int\ndicFrecuencias xs = M.fromListWith (+) (zip xs (repeat 1))\n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\nocurrenciasElementos4 :: Ord a => [a] -> [(a,Int)]\nocurrenciasElementos4 = foldl aux []\n where\n aux [] y = [(y,1)]\n aux ((x,k):xs) y | x == y = (x, k + 1) : xs\n | otherwise = (x, k) : aux xs y\n\n-- Equivalencia de las definiciones\n-- ================================\n\n-- La propiedad es\nprop_ocurrenciasElementos :: [Integer] -> Bool\nprop_ocurrenciasElementos xs =\n all (== (ocurrenciasElementos1 xs))\n [f xs | f <- [ocurrenciasElementos2,\n ocurrenciasElementos3,\n ocurrenciasElementos4]]\n\n-- La comprobaci\u00f3n es\n-- \u03bb> quickCheck prop_ocurrenciasElementos\n-- +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n-- \u03bb> last (ocurrenciasElementos1 (show (product [1..10^5])))\n-- ('5',42935)\n-- (7.93 secs, 11,325,169,512 bytes)\n-- \u03bb> last (ocurrenciasElementos2 (show (product [1..10^5])))\n-- ('5',42935)\n-- (8.46 secs, 11,750,911,592 bytes)\n-- \u03bb> last (ocurrenciasElementos3 (show (product [1..10^5])))\n-- ('5',42935)\n-- (8.29 secs, 11,447,015,896 bytes)\n-- \u03bb> last (ocurrenciasElementos4 (show (product [1..10^5])))\n-- ('5',42935)\n-- (9.97 secs, 12,129,527,912 bytes)\n<\/pre>\n