Punto de inflexión
Definir la función
|
1 |
inflexion :: Ord a => [a] -> Maybe a |
tal que (inflexion xs) es el primer elemento de la lista en donde se cambia de creciente a decreciente o de decreciente a creciente y Nothing si no se cambia. Por ejemplo,
|
1 2 3 4 |
inflexion [2,2,3,5,4,6] == Just 4 inflexion [9,8,6,7,10,10] == Just 7 inflexion [2,2,3,5] == Nothing inflexion [5,3,2,2] == Nothing |
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 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 |
import Data.List (find) import Data.Maybe (isJust, fromJust) -- 1ª solución -- =========== inflexion :: Ord a => [a] -> Maybe a inflexion (x:y:zs) | x == y = inflexion (y:zs) | x < y = decreciente (y:zs) | otherwise = creciente (y:zs) inflexion _ = Nothing -- (creciente xs) es el segundo elemento de la primera parte creciente -- de xs y Nothing, en caso contrario. Por ejemplo, -- creciente [4,3,5,6] == Just 5 -- creciente [4,3,5,2,7] == Just 5 -- creciente [4,3,2] == Nothing creciente (x:y:zs) | x >= y = creciente (y:zs) | otherwise = Just y creciente _ = Nothing -- (decreciente xs) es el segundo elemento de la primera parte -- decreciente de xs y Nothing, en caso contrario. Por ejemplo, -- decreciente [4,2,3,1,0] == Just 2 -- decreciente [4,5,3,1,0] == Just 3 -- decreciente [4,5,7] == Nothing decreciente (x:y:zs) | x <= y = decreciente (y:zs) | otherwise = Just y decreciente _ = Nothing -- 2ª solución -- =========== inflexion2 :: Ord a => [a] -> Maybe a inflexion2 = aux . signos where aux [] = Nothing aux ((s,_):ys) | null zs = Nothing | otherwise = Just (snd (head zs)) where zs = dropWhile (\(p,_) -> p == s) ys -- (signos xs) es la lista de los pares dormado por el signo de -- crecimiento o decrecimiento de cada elemento de xs respecto de su -- anterior. Por ejemplo, -- λ> signos [2,2,2,3,5,5,4,5,2] -- [(1,3),(1,5),(-1,4),(1,5),(-1,2)] signos :: Ord a => [a] -> [(Int,a)] signos xs = [(signo x y,y) | (x,y) <- zip xs (tail xs), x /= y] -- (signo x y) es el signo de crecimiento o decrecimiento de y respecto -- de x. signo :: Ord a => a -> a -> Int signo x y | x > y = 1 | x < y = -1 | otherwise = 0 -- 3ª solución -- =========== inflexion3 :: Ord a => [a] -> Maybe a inflexion3 (x:y:xs) | x == y = inflexion3 $ y:xs | x < y = buscaMenor $ y:xs | otherwise = buscaMayor $ y:xs inflexion3 _ = Nothing buscaMenor :: Ord a => [a] -> Maybe a buscaMenor (y:xs) | isJust busca = Just (snd (fromJust busca)) | otherwise = Nothing where busca = find parDecreciente (zip (y:xs) xs) buscaMayor :: Ord a => [a] -> Maybe a buscaMayor (y:xs) | isJust busca = Just (snd (fromJust busca)) | otherwise = Nothing where busca = find parCreciente (zip (y:xs) xs) parCreciente :: Ord a => (a,a) -> Bool parCreciente (a,b) = a < b parDecreciente :: Ord a => (a,a) -> Bool parDecreciente (a,b) = a > b -- Comparación de eficiencia -- ========================= -- λ> inflexion (replicate (10^7) 5 ++ [0,1]) -- Just 1 -- (4.73 secs, 3,360,141,912 bytes) -- λ> inflexion2 (replicate (10^7) 5 ++ [0,1]) -- Just 1 -- (2.71 secs, 2,480,144,352 bytes) -- λ> inflexion3 (replicate (10^7) 5 ++ [0,1]) -- Just 1 -- (5.06 secs, 3,360,143,680 bytes) -- -- λ> inflexion ([1..10^7] ++ [0,1]) -- Just 0 -- (3.60 secs, 3,120,146,728 bytes) -- λ> inflexion2 ([1..10^7] ++ [0,1]) -- Just 0 -- (11.33 secs, 6,480,143,376 bytes) -- λ> inflexion3 ([1..10^7] ++ [0,1]) -- Just 0 -- (3.28 secs, 3,280,140,784 bytes) -- -- λ> inflexion ([10^7,10^7-1..1] ++ [2,1]) -- Just 2 -- (3.62 secs, 3,200,141,784 bytes) -- λ> inflexion2 ([10^7,10^7-1..1] ++ [2,1]) -- Just 2 -- (10.01 secs, 5,840,144,200 bytes) -- λ> inflexion3 ([10^7,10^7-1..1] ++ [2,1]) -- Just 2 -- (3.56 secs, 3,360,145,728 bytes) |