Menu Close

Vecino en lista circular

José A. Alonso,

En la lista circular [3,2,5,7,9]

  • el vecino izquierdo de 5 es 2 y su vecino derecho es 7,
  • el vecino izquierdo de 9 es 7 y su vecino derecho es 3,
  • el vecino izquierdo de 3 es 9 y su vecino derecho es 2,
  • el elemento 4 no tiene vecinos (porque no está en la lista).

Para indicar las direcciones se define el tipo de datos

   data Direccion = I | D deriving Eq

Definir la función

   vecino :: Eq a => Direccion -> [a] -> a -> Maybe a

tal que (vecino d xs x) es el vecino de x en la lista de elementos distintos xs según la dirección d. Por ejemplo,

   vecino I [3,2,5,7,9] 5  ==  Just 2
   vecino D [3,2,5,7,9] 5  ==  Just 7
   vecino I [3,2,5,7,9] 9  ==  Just 7
   vecino D [3,2,5,7,9] 9  ==  Just 3
   vecino I [3,2,5,7,9] 3  ==  Just 9
   vecino D [3,2,5,7,9] 3  ==  Just 2
   vecino I [3,2,5,7,9] 4  ==  Nothing
   vecino D [3,2,5,7,9] 4  ==  Nothing

Soluciones

data Direccion = I | D deriving Eq
 
-- 1ª solución
-- ===========
 
vecino1 :: Eq a => Direccion -> [a] -> a -> Maybe a
vecino1 d xs x = busca x (vecinos d xs)
 
-- (vecinos d xs) es la lista de elementos de xs y sus vecinos según la
-- direccioń d. Por ejemplo,
--    vecinos I [1..5]  ==  [(2,1),(3,2),(4,3),(5,4),(1,5)]
--    vecinos D [1..5]  ==  [(1,2),(2,3),(3,4),(4,5),(5,1)]
vecinos :: Direccion -> [a] -> [(a,a)]
vecinos I xs = zip (tail (cycle xs)) xs
vecinos D xs = zip xs (tail (cycle xs))
 
-- (busca x ps) es el la segunda componente de primer par de ps cuya
-- primera componente es igual a x. Por ejemplo, 
--    busca 3 [(4,1),(3,2),(3,7)]  ==  Just 2
--    busca 7 [(4,1),(3,2),(3,7)]  ==  Nothing
busca :: Eq a => a -> [(a,b)] -> Maybe b
busca x ps
  | null zs   = Nothing
  | otherwise = Just (head zs)
  where zs = [z | (x',z) <- ps, x' == x]
 
-- 2ª solución
-- ===========
 
vecino2 :: Eq a => Direccion -> [a] -> a -> Maybe a
vecino2 d xs x = lookup x (vecinos d xs)
 
-- 3ª solución
-- ===========
 
vecino3 :: Eq a => Direccion -> [a] -> a -> Maybe a
vecino3 I xs x = lookup x (zip (tail (cycle xs)) xs) 
vecino3 D xs x = lookup x (zip xs (tail (cycle xs)))
Posted in Medio
Tagged , , , , , , , ,

10 Comments

  1. pabhueacu
    Responder 
    data Direccion = I | D deriving Eq
 
vecino :: Eq a => Direccion -> [a] -> a -> Maybe a
vecino d xs e
  | e `elem` xs = if d == I
                  then auxI (last xs : xs) e
                  else auxD (xs ++ [head xs]) e
  | otherwise   = Nothing
  where auxD (x:y:xs) e  | x == e    = Just y
                         | otherwise = auxD (y:xs) e
        auxI (x:y:xs) e  | y == e    = Just x
                         | otherwise = auxI (y:xs) e
  2. angruicam1
    Responder 
    import Data.Maybe (isJust, fromJust)
import Data.List (elemIndex)
 
data Direccion = I | D deriving Eq
 
vecino :: Eq a => Direccion -> [a] -> a -> Maybe a
vecino D (y:xs) x
  | x == last xs = Just y
  | isJust busca = Just $ (y:xs) !! (succ . fromJust $ busca)
  | otherwise    = Nothing
  where busca = elemIndex x (y:xs)
vecino I (y:xs) x
  | x == y       = Just $ last xs
  | isJust busca = Just $ (y:xs) !! (pred . fromJust $ busca)
  | otherwise    = Nothing
  where busca = elemIndex x (y:xs)
  3. Chema Cortés
    Responder 
    shiftL :: [a] -> [a]
shiftL = (++) <$> tail <*> return . head
 
vecino :: Eq a => Direccion -> [a] -> a -> Maybe a
vecino _ [] = const Nothing
vecino I xs = flip lookup $ zip (shiftL xs) xs
vecino D xs = flip lookup $ zip xs (shiftL xs)
  4. menvealer
    Responder 
    vecino :: Eq a => Direccion -> [a] -> a -> Maybe a
vecino I xs n = anterior xs n
vecino D xs n = siguiente xs n
 
anterior :: Eq a => [a] -> a -> Maybe a
anterior (x:xs) n | notElem n (x:xs) = Nothing
                  | n == x           = Just (last xs)
                  | n == head xs     = Just x
                  | otherwise        = anterior xs n
 
siguiente :: Eq a => [a] -> a -> Maybe a
siguiente (x:xs) n | notElem n (x:xs) = Nothing
                   | n == x           = Just (head xs)
                   | n == last xs     = Just x
                   | otherwise        = siguiente xs n
  5. agumaragu1
    Responder 
    data Direccion = I | D deriving Eq
 
vecino :: Eq a => Direccion -> [a] -> a -> Maybe a
vecino d xs x
  | notElem x xs = Nothing
  | d == D       = Just (aux xs)
  | d == I       = Just (aux (reverse xs))
  where aux ps = ((dropWhile (/= x) (cycle ps))!!1)
  6. josmoncos
    Responder 
    data Direccion = I | D deriving Eq
 
vecino :: Eq a => Direccion -> [a] -> a -> Maybe a
vecino D xs y | y == last xs = Just $ head xs 
              | elem y xs    = Just $ head (tail (dropWhile (/= y) xs))
              | otherwise    = Nothing
vecino I xs y | y == head xs = Just $ last xs
              | elem y xs    = Just $ last (takeWhile (/= y) xs)
              | otherwise    = Nothing
  7. antgongar
    Responder 
    vecino :: Eq a => Direccion -> [a] -> a -> Maybe a
vecino I xs x = lookup x (zip (tail (cycle xs)) xs) 
vecino D xs x = lookup x (zip xs (tail (cycle xs)))
  8. rocruimon
    Responder 
     
data Direccion = I | D deriving Eq
 
vecino :: Eq a => Direccion -> [a] -> a -> Maybe a
vecino _ [] _ = Nothing
vecino I xs n | not (elem n xs) = Nothing
              | otherwise = vecinoizquierdo xs n
vecino D xs n | not (elem n xs) = Nothing
              |otherwise = vecinoizquierdo (reverse xs) n 
 
vecinoizquierdo [] n = Nothing
vecinoizquierdo xs n
  | takeWhile (/=n) xs == [] = Just (last xs)
  | otherwise = Just (last (takeWhile (/= n) xs))
  9. esppercab
    Responder 
    data Direccion = I | D deriving Eq
vecino :: Eq a => Direccion -> [a] -> a -> Maybe a
vecino d [] x = Nothing
vecino d xs x |x `elem` xs   = aux d xs x
              |otherwise      = Nothing
 
aux :: Eq a => Direccion -> [a] -> a -> Maybe a
aux I xs x |x == head xs    = Just $ last xs
           |otherwise       = Just $ last (takeWhile (/= x) xs)
 
aux D xs x |x == last xs   = Just $ head xs
           |otherwise      = Just $ (dropWhile (/= x) xs) !! 1
  10. carriomon1
    Responder 
    import Data.Maybe (fromJust)
 
vecino :: Eq a => Direccion -> [a] -> a -> Maybe a
vecino d xs x
  | notElem x xs = Nothing
  | d == D       = Just (head (drop (fromJust (elemIndex x xs)  + 1) (xs++xs)))
  | d == I       = vecino D (reverse xs) x   
  | otherwise    = Nothing

Escribe tu solución

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