Menu Close

Punto de inflexión

 

Definir la función

   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,

   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

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)
Medio

22 soluciones de “Punto de inflexión

  1. alerodrod5
     
    inflexion :: Ord a => [a] -> Maybe a
    inflexion (x:y:xs) | x < y = decreciente (y:xs)
                       | x == y = inflexion (y:xs)
                       | otherwise = creciente (y:xs)
    inflexion _ = Nothing
     
    creciente :: Ord a => [a] -> Maybe a
    creciente (x:y:xs) | x < y = Just y
                       | otherwise = creciente (y:xs)
    creciente _ = Nothing
     
     
    decreciente :: Ord a => [a] -> Maybe a
    decreciente (x:y:xs) | x > y = Just y
                         | otherwise = decreciente (y:xs)
    decreciente _ = Nothing
    • jaibengue

      Puede optimizarse si cambias las lineas 3 y 4, 9 y 10, 15 y 16, tal que así:

      inflexion (x:y:xs) | x == y = inflexion (y:xs)
                         | x < y  = decreciente (y:xs)
      -- 
      creciente (x:y:xs) | x >= y    = creciente (y:xs)
                         | otherwise = Just y
      --
      decreciente (x:y:xs) | x <= y    = decreciente (y:xs)
                           | otherwise = Just y

      El por qué te lo dejo como ejercicio ^^

      • alefermar

        Los tiempos de las dos definiciones son casi iguales

        λ> inflexion1 ([1..2*10^6] ++ [0])
        Just 0
        (2.88 secs, 624,141,072 bytes)
        λ> inflexion2 ([1..2*10^6] ++ [0])
        Just 0
        (2.89 secs, 624,142,032 bytes)

        El primero es con la definición de alerodrod5 y el segundo con la de jaibengue.

        • jaibengue

          Hay CIERTAS listas para las que la definición de alerodrod5 no es del todo eficiente.
          En una lista suficientemente grande en el que todos los elementos sean el mismo, por ejemplo.

  2. angruicam1
    inflexion :: Ord a => [a] -> Maybe a
    inflexion (x:y:xs) | x <= y = crece (y:xs)
                               | x >= y = decrece (y:xs)
     
    crece :: Ord a => [a] -> Maybe a
    crece [_]         = Nothing
    crece (x:y:xs) | x <= y       = crece (y: xs)
                           | otherwise = Just y
     
    decrece :: Ord a => [a] -> Maybe a
    decrece [_]         = Nothing
    decrece (x:y:xs) | x >= y       = decrece (y:xs)
                               | otherwise = Just y
    • angruicam1

      La primera función no cubre casos de listas de dos elementos iguales, y la segunda no cubre la lista vacía ni listas de un elemento. La siguiente solución arregla estos casos:

      inflexion :: Ord a => [a] -> Maybe a
      inflexion (x:y:xs) | x <= y = crece (y:xs)
                         | x >= y = decrece (y:xs)
      inflexion _        = Nothing
       
      crece :: Ord a => [a] -> Maybe a
      crece [_]      = Nothing
      crece (x:y:xs) | x <= y    = crece (y:xs)
                     | otherwise = Just y
       
      decrece :: Ord a => [a] -> Maybe a
      decrece [_]      = Nothing
      decrece (x:y:xs) | x >= y    = decrece (y:xs)
                       | otherwise = Just y
        • angruicam1

          Sí ya, sería más bien esta definición:

          inflexion :: Ord a => [a] -> Maybe a
          inflexion (x:y:xs) | x < y  = crece (y:xs)
                             | x > y  = decrece (y:xs)
                             | x == y = inflexion (y:xs)
          inflexion _        = Nothing
           
          crece :: Ord a => [a] -> Maybe a
          crece (x:y:xs) | x <= y    = crece (y:xs)
                         | otherwise = Just y
          crece _        = Nothing
           
          decrece :: Ord a => [a] -> Maybe a
          decrece (x:y:xs) | x >= y    = decrece (y:xs)
                           | otherwise = Just y
          decrece _        = Nothing
          • jaibengue

            Te digo lo mismo que a alerodrod5, la linea en la que

            | x == y = inflexion (y:xs)

            debería ser la primera comprobación en la función inflexion.

  3. jaibengue

    Dos definiciones:
    Una primera, quizá mas intuitiva, lineal en (length [a]) , y una segunda, aunque también lineal en (length [a]), ligeramente mas eficiente:

    inflexion :: Ord a => [a] -> Maybe a
    inflexion (x:y:z:xs)  | x<=y && y<=z = inflexion (y:z:xs)
                          | x<=y && y>z  = Just z
                          | x>y && y>=z  = inflexion (y:z:xs)
                          | x>y && y<z   = Just z
    inflexion _           = Nothing
     
    inflexionEficiente :: Ord a => [a] -> Maybe a
    inflexionEficiente (x:y:xs) | x==y = inflexionEficiente (y:xs)
                                | x<y  = cre (y:xs)
                                | x>y  = dec (y:xs)
      where cre (p:q:xs) | p<=q      = cre (q:xs)
                         | otherwise = Just q
            cre _        = Nothing
     
            dec (p:q:xs) | p>=q      = dec (q:xs)
                         | otherwise = Just q
            dec _        = Nothing
     
    inflexionEficiente _ = Nothing
    • angruicam1

      Buenas, la definición de inflexion no es correcta. Por ejemplo:

      λ> inflexion3 [2,2,1]
      Just 1

      Cuando debería devolver Nothing.
      Empleando la misma idea se me ocurre definir:

      inflexion :: Ord a => [a] -> Maybe a
      inflexion (x:y:z:xs) | puntoInflexion [x,y,z] = Just z
                           | otherwise              = inflexion2 (y:z:xs)
      inflexion _          = Nothing
       
      puntoInflexion :: Ord a => [a] -> Bool
      puntoInflexion [x,y,z] = (y < x && y < z) || (y > x && y > z)
      • alefermar

        Falla por ejemplo en [3,1,1,4]

        λ> inflexion [3,1,1,4]
        Nothing

        Debería de dar Just 4

        • angruicam1

          Ciertamente usando esta idea habría que añadirle el caso de que el punto de inflexión sea el último elemento de la lista, por tanto (si no me he vuelto a equivocar) debería ser:

          inflexion :: Ord a => [a] -> Maybe a
          inflexion (x:y:z:xs)
            | null xs && ((x >= y && y < z) || (x <= y && y > z)) = Just z 
            | (y < x && y < z) || (y > x && y > z)                = Just z
            | otherwise                                           = inflexion (y:z:xs)
          inflexion _          = Nothing
    • alefermar

      En la evaluación no se aprecia que la inflexionEficiente mejore notablemente el tiempo respecto de la primera definición de alerodrod5

      λ> inflexion ([1..2*10^6] ++ [0])
      Just 0
      (2.87 secs, 624,141,920 bytes)
      λ> inflexionEficiente ([1..2*10^6] ++ [0])
      Just 0
      (2.85 secs, 624,141,392 bytes)
      • angruicam1

        Realmente sí lo hace, lo que pasa que no en todos los casos. Por ejemplo en este caso sí es más eficiente:

        λ> inflexion $ replicate (10^7) 5 ++ [0,1]
        Just 1
        (14.39 secs, 3,920,115,104 bytes)
        λ> inflexionEficiente $ replicate (10^7) 5 ++ [0,1]
        Just 1
        (11.41 secs, 3,840,117,440 bytes)

        La cuestión de esto es que cada vez que la función inflexion toma dos valores y los compara no sabe de por sí si son menores, mayores o iguales. Con esto quiero decir que primero comprobara en el caso de la función inflexion si x < y, y si no lo es pasará a comprobar si son iguales y en caso de no serlo aplicaría el otherwise. En el caso de inflexionEficiente comprobaría primero la igualdad y posteriormente que x < y, de ahí la mejora que se aprecia en el ejemplo que he puesto (pues se ahorra comprobar cada vez que aplica la función que x < y = False).

        Por otro lado, la mejora de Jaime se basa (si no me equivoco) en que solo en el caso de que x == y se vuelve a aplicar la función inflexion, pues en otro caso pasaría a aplicar la función creciente o decreciente. Por tanto nada más que x sea distinto de y la función inflexion no se vuelve a aplicar, mientras que si son iguales se aplicará un número determinado de veces (en la que si compruebas x < y antes que x == y irás perdiendo eficiencia).

        En el caso de las funciones creciente o decreciente yo diría que la eficiencia no varía pues si un caso es falso se va directamente al otro. La única variación que observo que podría darse es que sea menos eficiente comparar x y (o viceversa), y en este caso sería más eficiente la función de Alejandro.

        No estoy seguro de si me he explicado demasiado bien pero espero que se entienda ^^ (y no estar equivocado).

  4. antgongar

    Se puede definir sin usar recursión y mejorar el tiempo de la definición inflexionEficiente de jaibengue en el ejemplo de angruicam1.

    inflexion :: Ord a => [a] -> Maybe a
    inflexion = aux . signos 
      where aux [] = Nothing
            aux ((s,_):ys) | null zs   = Nothing
                           | otherwise = Just (snd (head zs))
              where zs = dropWhile ((p,_) -> p == s) ys
     
    --    λ> 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 :: Ord a => a -> a -> Int
    signo x y | x > y     = 1
              | x < y     = -1
              | otherwise = 0

    La comparación de tiempos es

    λ> inflexionEficiente (replicate (10^7) 5 ++ [0,1])
    Just 1
    (21.90 secs, 3,840,142,536 bytes)
    λ> inflexionA6 (replicate (10^7) 5 ++ [0,1])
    Just 1
    (8.04 secs, 2,480,147,656 bytes)
  5. agumaragu1
     
    inflexion :: Num a => Ord  a => [a] -> Maybe a
    inflexion xs = aux xs 0
      where aux (x:y:xs) n | n*(x-y) < 0 = Just y
                           | otherwise   = aux (y:xs) (x-y)
            aux _ _ = Nothing
    • agumaragu1

      Esa sólo sirve para listas numéricas, pero con la misma idea se hace

       
      inflexion2 :: Ord  a => [a] -> Maybe a
      inflexion2 xs = aux xs 0
        where aux (x:y:xs) n | n*sig < 0 = Just y
                             | otherwise   = aux (y:xs) sig
                where sig | x > y = 1
                          | x == y = 0
                          | x < y = -1
              aux _ _ = Nothing

      Esta sirve para cualquier dato de tipo Ord pero es menos eficiente en valores numéricos que la primera.

  6. angruicam1

    Otra definición que podría proponerse sería la siguiente:

    import Data.List (find)
    import Data.Maybe (fromJust)
     
    inflexion :: Ord  a => [a] -> Maybe a
    inflexion (x:y:xs) | x == y = inflexion3 $ y:xs
                       | x < y  = buscaMenor $ y:xs
                       | otherwise = buscaMayor $ y:xs
     
    buscaMenor :: Ord a => [a] -> Maybe a
    buscaMenor (y:xs) | busca /= Nothing = Just $ snd . fromJust $ busca
                      | otherwise = Nothing
                        where busca = find parDecreciente $ zip (y:xs) xs
     
    buscaMayor :: Ord a => [a] -> Maybe a
    buscaMayor (y:xs) | busca /= Nothing = 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 la eficiencia:

    -- Lista constante
    λ> inflexion $ replicate (10^7) 5 ++ [0,1]
    Just 1
    (11.28 secs, 3,360,117,472 bytes)
    λ> inflexion3 $ replicate (10^7) 5 ++ [0,1]
    Just 1
    (11.31 secs, 3,600,118,984 bytes)
    λ> inflexion4 $ replicate (10^7) 5 ++ [0,1]
    Just 1
    (6.75 secs, 2,480,119,392 bytes)
     
    -- Lista creciente
    λ> inflexion $ [1..10^7] ++ [0,1]
    Just 0
    (10.06 secs, 3,120,114,960 bytes)
    λ> inflexion3 $ [1..10^7] ++ [0,1]
    Just 0
    (7.22 secs, 3,280,118,584 bytes)
    λ> inflexion4 $ [1..10^7] ++ [0,1]
    Just 0
    (29.17 secs, 6,480,118,008 bytes)
     
    -- Lista decreciente
    λ> inflexion $ reverse [1..10^7] ++ [2,1]
    Just 2
    (12.75 secs, 3,360,114,512 bytes)
    λ> inflexion3 $ reverse [1..10^7] ++ [2,1]
    Just 2
    (8.39 secs, 3,520,116,480 bytes)
    λ> inflexion4 $ reverse [1..10^7] ++ [2,1]
    Just 2
    (27.61 secs, 6,000,114,128 bytes)

    Donde inflexion es la función inflexionEficiente de jaibengue, inflexion3 es mi propuesta de solución e inflexion4 es la función inflexion de antgongar.

    • antgongar

      En la definición de inflexion falta el caso de listas con menos de dos elementos.

      Además, en el caso en que los dos primeros elementos sean iguales, en lugar de inflexion3 debe de ser inflexion.

      A parte de esos dos pequeños detalles, es la solución que más me gusta.

      • angruicam1

        Cierto, habría que dejar la definición así:

        inflexion :: Ord  a => [a] -> Maybe a
        inflexion (x:y:xs) | x == y = inflexion $ y:xs
                           | x < y  = buscaMenor $ y:xs
                           | otherwise = buscaMayor $ y:xs
        inflexion _        = Nothing

        Gracias por el comentario ^^

Los comentarios están cerrados.