Menu Close

Elemento más cercano que cumple una propiedad

-- Definir la función
--    cercano :: (a -> Bool) -> Int -> [a] -> Maybe a
-- tal que (cercano p n xs) es el elemento de xs más cercano a n que
-- verifica la propiedad p. La búsqueda comienza en n y los elementos se
-- analizan en el siguiente orden: n, n+1, n-1, n+2, n-2,... Por ejemplo, 
--    cercano (`elem` "aeiou") 6 "Sevilla"     ==  Just 'a'
--    cercano (`elem` "aeiou") 1 "Sevilla"     ==  Just 'e'
--    cercano (`elem` "aeiou") 2 "Sevilla"     ==  Just 'i'
--    cercano (`elem` "aeiou") 5 "Sevilla"     ==  Just 'a'
--    cercano (`elem` "aeiou") 9 "Sevilla"     ==  Just 'a'
--    cercano (`elem` "aeiou") (-3) "Sevilla"  ==  Just 'e'
--    cercano (>100) 4 [200,1,150,2,4]         ==  Just 150
--    cercano even 5 [1,3..99]                 ==  Nothing

Soluciones

import Data.List
 
-- 1ª solución
-- ===========
 
cercano1 :: (a -> Bool) -> Int -> [a] -> Maybe a
cercano1 p n xs | null ys   = Nothing
                | otherwise = Just (head ys)
    where ys = filter p (ordenaPorCercanos xs n)
 
-- (ordenaPorCercanos xs n) es la lista de los elementos de xs que
-- ocupan las posiciones n, n+1, n-1, n+2, n-2... Por ejemplo, 
--    ordenaPorCercanos [0..9] 4     ==  [4,5,3,6,2,7,1,8,0,9]
--    ordenaPorCercanos [0..9] 7     ==  [7,8,6,9,5,4,3,2,1,0]
--    ordenaPorCercanos [0..9] 2     ==  [2,3,1,4,0,5,6,7,8,9]
--    ordenaPorCercanos [0..9] (-3)  ==  [0,1,2,3,4,5,6,7,8,9]
--    ordenaPorCercanos [0..9] 20    ==  [9,8,7,6,5,4,3,2,1,0]
ordenaPorCercanos :: [a] -> Int -> [a]
ordenaPorCercanos xs n 
    | n < 0          = xs
    | n >= length xs = reverse xs
    | otherwise      = z : intercala zs (reverse ys)
    where (ys,(z:zs)) = splitAt n xs
 
-- (intercala xs ys) es la lista obtenida intercalando los elementos de
-- las lista xs e ys. Por ejemplo,
--    intercala [1..4] [5..10]   ==  [1,5,2,6,3,7,4,8,9,10]
--    intercala [5..10] [1..4]   ==  [5,1,6,2,7,3,8,4,9,10]
intercala :: [a] -> [a] -> [a]
intercala [] ys = ys
intercala xs [] = xs
intercala (x:xs) (y:ys) = x : y : intercala xs ys
 
-- 2ª solución (usando find)
-- =========================
 
cercano2 :: (a -> Bool) -> Int -> [a] -> Maybe a
cercano2 p n xs = find p (ordenaPorCercanos xs n)

Referencia

El ejercicio está basado en el problema del 12 de mayo de 1HaskellADay.

3 soluciones de “Elemento más cercano que cumple una propiedad

  1. María Ruiz
    cercano :: (Eq a) => (a -> Bool) -> Int -> [a] -> Maybe a
    cercano p n xs | null zs   = Nothing
                   | otherwise = head zs
        where m = length xs
              ps = posiciones n
              ks = menorSegContiene 0 (m-1) ps
              zs = [y | y <- seleccionaSegunPosicion ks xs, 
                        y /= Nothing, let Just z = y in p z]
     
    posiciones :: Int -> [Int]
    posiciones n = n:concat[[n+k,n-k] | k <-[1..]]
     
    menorSegContiene :: Eq a => a -> a -> [a] -> [a]
    menorSegContiene x y xs =
        head [ys | ys <-inits xs, elem x ys, elem y ys]
     
    seleccionaSegunPosicion :: [Int] -> [a] -> [Maybe a]
    seleccionaSegunPosicion [] xs = []
    seleccionaSegunPosicion (k:ks) xs 
        | k < 0 || k >= m  = Nothing:(seleccionaSegunPosicion ks xs)
        | otherwise = (Just (xs!!k)):(seleccionaSegunPosicion ks xs)
        where m = length xs
  2. María Ruiz

    La definición anterior corregida:

    cercano :: (a -> Bool) -> Int -> [a] -> Maybe a
    cercano p n xs | null zs   = Nothing
                   | otherwise = Just (head zs)
        where m  = length xs
              zs = [x | x <- listaDesde xs n, p x]
     
    listaDesde :: [a] -> Int -> [a]
    listaDesde xs k | k >= length xs -1 = reverse xs
                    | k <= 0            = xs
                    | otherwise         = z:intercala zs (reverse ys)
        where (ys,(z:zs)) = splitAt k xs
     
    intercala :: [a] -> [a] -> [a]
    intercala xs []         = xs
    intercala [] ys         = ys
    intercala (x:xs) (y:ys) = x:y:(intercala xs ys)
  3. David Argullo
    cercano :: (a -> Bool) -> Int -> [a] -> Maybe a
    cercano p n xs = aux p  (mezcla ys zs)
     where zs = drop (n+1) xs
           ys = reverse $ take (n+1) xs
           aux _  [] = Nothing
           aux p (x:xs) |p x = Just x
                        |otherwise = aux p xs
     
    mezcla :: [t] -> [t] -> [t]
    mezcla ys [] = ys
    mezcla [] zs = zs
    mezcla (y:ys) (z:zs) = y:z:mezcla ys zs

Escribe tu solución

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