Menu Close

Siguiente elemento en una lista

Definir la función

   siguiente :: Eq a => a -> [a] -> Maybe a

tal que (siguiente x ys) es justo el elemento siguiente a la primera ocurrencia de x en ys o Nothing si x no pertenece a ys. Por ejemplo,

   siguiente 5 [3,5,2,5,7]                       ==  Just 2
   siguiente 9 [3,5,2,5,7]                       ==  Nothing
   siguiente 'd' "afdegdb"                       ==  Just 'e'
   siguiente "todo" ["En","todo","la","medida"]  ==  Just "la"
   siguiente "nada" ["En","todo","la","medida"]  ==  Nothing
   siguiente 999999 [1..1000000]                 ==  Just 1000000
   siguiente 1000000 [1..1000000]                ==  Nothing

Soluciones

import Data.Maybe (listToMaybe) -- Para la 4ª solución
 
-- 1ª solución (por recursión):
siguiente1 :: Eq a => a -> [a] -> Maybe a
siguiente1 x (y1:y2:ys) | x == y1   = Just y2
                        | otherwise = siguiente1 x (y2:ys)
siguiente1 x _ = Nothing
 
-- 2ª solución (por comprensión):
siguiente2 :: Eq a => a -> [a] -> Maybe a
siguiente2 x ys 
    | null zs   = Nothing
    | otherwise = Just (snd (head zs))
    where zs = [(u,v) | (u,v) <- zip ys (tail ys), u == x]  
 
-- 3ª solución (con dropWhile)
siguiente3 :: Eq a => a -> [a] -> Maybe a
siguiente3 x = aux . drop 1 . dropWhile (/=x)
    where aux []    = Nothing
          aux (y:_) = Just y
 
-- 4ª solución (con dropWhile y listToMaybe):
siguiente4 :: Eq a => a -> [a] -> Maybe a
siguiente4 x = listToMaybe . drop 1 . dropWhile (/=x)
 
-- Nota: En la librería Data.Maybe está definida la función 
--    listToMaybe :: [a] -> Maybe a 
-- tal que (listToMaybe xs) es Nothing si la lista xs está vacía y es
-- justo el primer elemento, en caso contrario, Por ejemplo,
--    listToMaybe []       ==  Nothing
--    listToMaybe [3,2,5]  ==  Just 3
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    ghci> let n=10^6 in siguiente1 (n-1) [1..n]
--    Just 1000000
--    (1.34 secs, 277352616 bytes)
--    
--    ghci> let n=10^6 in siguiente2 (n-1) [1..n]
--    Just 1000000
--    (1.45 secs, 340836576 bytes)
--    
--    ghci> let n=10^6 in siguiente3 (n-1) [1..n]
--    Just 1000000
--    (0.26 secs, 84987544 bytes)
--    
--    ghci> let n=10^6 in siguiente4 (n-1) [1..n]
--    Just 1000000
--    (0.26 secs, 84987440 bytes)

5 soluciones de “Siguiente elemento en una lista

  1. jneira

    Aprovechando que Maybe es una mónada

    import Data.List (elemIndex)
    import Control.Monad (guard)
     
    siguiente :: Eq a => a -> [a] -> Maybe a
    siguiente x xs = do
      i <- elemIndex x xs
      guard (i < length xs - 1)
      return $ xs !! (i+1)

    Usando monad comprehension

    {-# LANGUAGE MonadComprehensions #-} 
     
    import Data.List (elemIndex)
     
    siguiente :: Eq a => a -> [a] -> Maybe a
    siguiente x xs = [xs!!(i+1) | i <- elemIndex x xs, i < length xs - 1]
  2. Diego
    import Data.List (elemIndex)
     
    siguiente :: Eq a => a -> [a] -> Maybe a
    siguiente p xs = elemIndex p xs >>= Just . (xs!!) . (+1)
    • jneira

      La definición es semánticamente equivalente a la primera salvo que no tiene la guarda (return == Just para Maybe). El no tener la guarda provoca que para el caso

      *Exercitium> siguiente 1000000 [1..1000000] 
      Just *** Exception: Prelude.(!!): index too large

      La desugarización de la notación con do de la versión monádica (con guarda) sería

      import Control.Monad (guard)
       
      siguiente x xs = 
          elemIndex x xs >>= i -> guard (i < length xs - 1) >> (return $ xs!!(i+1))
  3. Abel Martín
    siguiente :: Eq a => a -> [a] -> Maybe a
    siguiente x (y1:y2:ys) | x == y1   = Just y2
                           | otherwise = siguiente x (y2:ys)
    siguiente x _ = Nothing
    • Jesús Navas Orozco
      siguiente :: Eq a => a -> [a] -> Maybe a
      siguiente x ys 
          | notElem x ys || p == length ys -1 = Nothing
          | otherwise                         = Just (ys!!(p+1))
          where p = head [y | (x1,y) <- zip ys [0..], x1 == x]

Leave a Reply to Abel Martín Cancel reply

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.