Подпоследовательность

isSubSeq :: (Eq a) => [a] -> [a] -> Bool
isSubSeq xs ys = (filter (\ y -> elem y xs) ys) == xs
 
Main> isSubSeq "abc" "qweadbc"
True
Main> isSubSeq "abc" "qweadcb"
False

{-# Language LambdaCase#-}
isSubSeq :: (Eq a) => [a] -> [a] -> Bool
isSubSeq x y = isSubSeq' (x,y) || isSubSeq' (y,x)
  where
    isSubSeq' :: (Eq a) => ([a],[a]) -> Bool
    isSubSeq' = \case
      (x:sx,y:sy) | x == y -> isSubSeq' (sx,sy)
      (x:sx,y:sy)          -> isSubSeq' (x:sx,sy)
      (x:sx,_)             -> False
      _                    -> True

isSubSeq' :: (Eq a) => [a] -> [a] -> Bool
isSubSeq' xs ys = (foldl (\ acc y -> if (elem y xs) && not (elem y acc) then acc++[y] else acc) [] ys) == xs 
 
isSubSeq :: (Eq a) => [a] -> [a] -> Bool
isSubSeq xs ys = foldl (\ acc k -> acc || isSubSeq' xs (drop k ys)) False [1..(length ys)-(length xs)+1]
 
Main> isSubSeq "abc" "aabac"
True
Main> isSubSeq "abc" "aabaccc"
True
Main> isSubSeq "abc" "caabaccc"
True
Main> isSubSeq "abc" "aaba"
False

isSubSeq :: (Eq a) => [a] -> [a] -> Bool
isSubSeq (x:sx) (y:sy) = isSubSeq (if x == y then sx else x:sx) sy
isSubSeq x      _      = null x

isSubs :: (Eq a) => [a] -> [a] -> Bool
isSubs xs ys = (foldl (\ acc y -> w acc y) xs ys) == []
               where w xx yy = if xx==[] then []
                            else if head xx == yy then tail xx
                                    else xx
 
Main> isSubs "abc" "baabcc"
True
Main> isSubs "abc" "bbcc"
False
Main> isSubs "abc" "aabac"
True
Main> isSubs "aabc" "ababac"
True
Main> isSubs "bca" "ababac"
False

isSubs :: (Eq a) => [a] -> [a] -> Bool
isSubs x y = null $ foldl 
  (\xs y -> case xs of
    x:sx | x == y -> sx
    _             -> xs) x y