boeingx / haskell-programming-from-first-principles Goto Github PK

isSubsequenceOf "blah" "wootbla" == False
isSubsequenceOf "blah" "halbwoot" == False

isSubsequenceOf "blah" "wootbla" == True
isSubsequenceOf "blah" "halbwoot" == True

  indexOf :: (Eq a) => a -> [a] -> Int
  indexOf x ys = case elemIndex x ys of 
    Just a -> a 
    Nothing -> -1

  splitBy :: (Eq a) => a -> [a] -> ([a], [a])
  splitBy x = span (/= x)

  joinWithout :: (Eq a) => a -> [a] -> [a]
  joinWithout x ys = let (a, b) = splitBy x ys in (a ++ tail b)  

  isSubseqOf :: (Eq a) => [a] -> [a] -> Bool
  isSubseqOf [] _ = True 
  isSubseqOf _ [] = False
  -- @TODO: strip each element of the referenced list after each recursion
  isSubseqOf (x : xs) ys 
    | null ys'' = False
    | otherwise = 
        case xs of 
          (z : _) -> 
            let idX = indexOf x ys
                idZ = indexOf z ys in
            case (compare idX idZ) of 
              LT -> isSubseqOf xs (joinWithout x ys)
              _  -> False
          _       -> isSubseqOf xs (joinWithout x ys)
    where (ys', ys'') = splitBy x ys