Good afternoon.
I need to create a function in Haskell that verifies that several elements are in that order in a given list.
That is:
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
I'm trying to do it with subsequences (Data.List), but it does not work as I pretend.
Warm regards. Thank you very much for your attention.
You can see the problem here:
isInList :: Eq a => a -> [a] -> Maybe [a] try to find x in xs and return the rest of the list (or fail if you can not find x ).
se_encuentra :: Eq a => [a] -> [a] -> Bool use multiple times to isInList to find all the values in xs and controls the final result is not Nothing
In se_encuentra you want to process your input from left to right so you have to use something like foldl and isInList can fail so you have to use foldlM (the monadic version of foldl ).
In other words (perhaps more understandable than my Spanish):
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)
With subsequences you get all the possible sequences of any length, including sequences that would give you false positives when doing the check.
For example, from [1,4,6,6,5,4,0,7] you get [5,4,7] as sequence. You need some way that the sequences are of elements followed, without jumps.
A simple way is to combine isPrefixOf with tails :
import Data.List (isPrefixOf, tails)
contiene :: Eq a => [a] -> [a] -> Bool
contiene xs ys = any (xs 'isPrefixOf') (tails ys)
What can be done more elegant like:
contiene :: Eq a => [a] -> [a] -> Bool
contiene xs = any (xs 'isPrefixOf') . tails