Máximos de una lista
Definir la función
|
1 |
maximos :: Ord a => [a] -> [a] |
tal que (maximos xs) es la lista de los elementos de xs que son mayores que todos sus anteriores. Por ejemplo,
|
1 2 3 4 |
maximos [1,-3,5,2,3,4,7,6,7] == [1,5,7] maximos "bafcdegag" == "bfg" maximos (concat (replicate (10^6) "adxbcde")++"yz") == "adxyz" length (maximos [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 |
import Data.List (inits, nub) -- 1ª definición (por comprensión) maximos1 :: Ord a => [a] -> [a] maximos1 xs = [x | (ys,x) <- zip (inits xs) xs, all (<x) ys] -- 2ª definición (por recursión) maximos2 :: Ord a => [a] -> [a] maximos2 [] = [] maximos2 (x:xs) = x : maximos2 (filter (>x) xs) -- 3ª definición (por recursión con acumulador) maximos3 :: Ord a => [a] -> [a] maximos3 [] = [] maximos3 (x:xs) = aux xs [x] x where aux [] zs _ = reverse zs aux (y:ys) zs m | y > m = aux ys (y:zs) y | otherwise = aux ys zs m -- 4ª definición (con scanl1): maximos4 :: Ord a => [a] -> [a] maximos4 = nub . scanl1 max -- Comparación de eficiencia -- ghci> maximos1 (concat (replicate (10^3) "adxbcde") ++ "yz") -- "adxyz" -- (5.82 secs, 2859603952 bytes) -- ghci> maximos2 (concat (replicate (10^3) "adxbcde") ++ "yz") -- "adxyz" -- (0.02 secs, 5879664 bytes) -- ghci> maximos3 (concat (replicate (10^3) "adxbcde") ++ "yz") -- "adxyz" -- (0.03 secs, 4153680 bytes) -- ghci> maximos4 (concat (replicate (10^3) "adxbcde") ++ "yz") -- "adxyz" -- (0.02 secs, 4163296 bytes) -- -- ghci> maximos2 (concat (replicate (10^6) "adxbcde") ++ "yz") -- "adxyz" -- (3.64 secs, 1314485320 bytes) -- ghci> maximos3 (concat (replicate (10^6) "adxbcde") ++ "yz") -- "adxyz" -- (6.59 secs, 1706434544 bytes) -- ghci> maximos4 (concat (replicate (10^6) "adxbcde") ++ "yz") -- "adxyz" -- (0.89 secs, 1594567000 bytes) -- -- ghci> length (maximos2 [1..10^4]) -- 10000 -- (17.34 secs, 4302913816 bytes) -- ghci> length (maximos3 [1..10^4]) -- 10000 -- (0.03 secs, 6602488 bytes) -- ghci> length (maximos4 [1..10^4]) -- 10000 -- (1.37 secs, 6820408 bytes) |