1

Buenas tardes. Necesito crear una función en Haskell que verifique que varios elementos se encuentran en dicho orden en una lista dada.

Es decir:

se_encuentra [5,4,7] [1,4,5,4,7,9,10] == True

se_encuentra [5,4,7] [1,4,6,6,5,4,0,7] == False

Lo intentando hacer con subsequences (Data.List), pero no funciona como pretendo.

Un cordial saludo. Muchas gracias por su atención.

2 respuestas 2

1

Con subsequences obtienes todas las secuencias posibles de cualquier longitud, incluyendo secuencias que te darían falsos positivos al hacer la comprobación.

Por ejemplo, de [1,4,6,6,5,4,0,7] obtienes [5,4,7] como secuencia. Necesitas alguna forma de que las secuencias sean de elementos seguidos, sin saltos.

Una forma simple es combinar isPrefixOf con tails:

import Data.List (isPrefixOf, tails)

contiene :: Eq a => [a] -> [a] -> Bool
contiene xs ys = any (xs `isPrefixOf`) (tails ys)

Que se puede hacer más elegante como:

contiene :: Eq a => [a] -> [a] -> Bool
contiene xs = any (xs `isPrefixOf`) . tails
0

Puedes ver el problemo aqui:

  • isInList :: Eq a => a -> [a] -> Maybe [a] intenta de encuentrar a x en xs y retorno el resto de la lista (o falla si no puede encuentrar a x).

  • se_encuentra :: Eq a => [a] -> [a] -> Bool usa multiples veces a isInList para encuentra todas las valores en xs y controls el resultado final no es Nothing

En se_encuentra quieres procesar a tu input de izquierda a derecha asi tienes que usar algo como foldl y isInList puede fallar asi tienes que usar foldlM (la monadic version de foldl).

En otras palabras (quizas mas comprensible que mi espanol):

import Data.Maybe
import Data.Foldable

isInList :: Eq a => a -> [a] -> Maybe [a]
isInList x xs = case dropWhile (x /=) xs of
  []         -> Nothing
  (_ : rest) -> Just rest

se_encuentra :: Eq a => [a] -> [a] -> Bool
se_encuentra xs ys = isJust (foldlM (flip isInList) ys xs)

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.