Máximos de una lista

Definir la función

   maximos :: Ord a => [a] -> [a]

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,

   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

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

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)

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)

4 Comentarios

maximos :: Ord a => [a] -> [a]
maximos [] = []
maximos (x:xs) = x : aux (x:xs)
    where aux (x:y:xs) | y > x     = y : aux (y:xs)
                       | otherwise = aux (x:xs)
          aux _ = []

maximos [] = []

maximos (x:xs) = x : aux (x:xs)

where aux (x:y:xs) | y > x = y : aux (y:xs)

| otherwise = aux (x:xs)

aux _ = []

Responder

maximos :: Ord a => [a] -> [a]
maximos = reverse . aux []
    where aux acc []    = acc
          aux [] (y:ys) = aux [y] ys
          aux p@(x:xs) (y:ys) | y > x     = aux (y:p) ys
                              | otherwise = aux p ys

maximos = reverse . aux []

where aux acc [] = acc

aux [] (y:ys) = aux [y] ys

aux p@(x:xs) (y:ys) | y > x = aux (y:p) ys

| otherwise = aux p ys

Jesús Navas Orozco dice:

22-junio-2015 a las 18:19

Haskell

maximos' :: Ord a => [a] -> [a] maximos' = nub .scanl1 max

1
2

maximos' :: Ord a => [a] -> [a]
maximos' = nub .scanl1 max

Responder

Chema Cortés dice:

23-junio-2015 a las 12:51

Haskell

maximos :: Ord a => [a] -> [a] maximos [] = [] maximos (x:xs) = x : maximos (dropWhile (x>=) xs)

1
2
3

maximos :: Ord a => [a] -> [a]
maximos [] = []
maximos (x:xs) = x : maximos (dropWhile (x>=) xs)

Responder

Máximos de una lista

Soluciones

4 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Se puede imprimir o compartir con

4 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico