Siguiente elemento en una lista

Definir la función

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

1	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

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)

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 Comentarios

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)

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]

{-# 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]

Responder

import Data.List (elemIndex)

siguiente :: Eq a => a -> [a] -> Maybe a
siguiente p xs = elemIndex p xs >>= Just . (xs!!) . (+1)

import Data.List (elemIndex)

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

siguiente p xs = elemIndex p xs >>= Just . (xs!!) . (+1)

Responder

jneira dice:

2-febrero-2015 a las 22:34

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

1
2

*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

Haskell

import Control.Monad (guard) siguiente x xs = elemIndex x xs >>= \i -> guard (i < length xs - 1) >> (return $ xs!!(i+1))

1
2
3
4

import Control.Monad (guard)

siguiente x xs =
elemIndex x xs >>= \i -> guard (i < length xs - 1) >> (return $ xs!!(i+1))

Responder

siguiente :: Eq a => a -> [a] -> Maybe a
siguiente x (y1:y2:ys) | x == y1   = Just y2
                       | otherwise = siguiente x (y2:ys)
siguiente x _ = Nothing

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

siguiente x (y1:y2:ys) | x == y1 = Just y2

| otherwise = siguiente x (y2:ys)

siguiente x _ = Nothing

Responder

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]

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]

Responder

Siguiente elemento en una lista

Soluciones

5 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Se puede imprimir o compartir con

5 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico