Sunday 5 June 2016

Haskell: Check whether a list is infix of other list


ListUtil.hs
isInfix :: Eq a => [a] -> [a] -> Bool
isInfix list1 list2 = checkInfix list1 (getTails list2)

checkInfix :: Eq a => [a] -> [[a]] -> Bool
checkInfix [] [] = True
checkInfix _ [] = False
checkInfix xs (y:ys) = isPrefix xs y || checkInfix xs ys

getTails :: [a] -> [[a]]
getTails [] = []
getTails list@(x:xs) = (list) : getTails (xs) 

isPrefix :: Eq a => [a] -> [a] -> Bool
isPrefix [] [] = True
isPrefix [] _ = True
isPrefix _ [] = False
isPrefix (x:xs) (y:ys) = (x==y) && (isPrefix xs ys)

*Main> :load ListUtil.hs 
[1 of 1] Compiling Main             ( ListUtil.hs, interpreted )
Ok, modules loaded: Main.
*Main> 
*Main> isInfix "ptr" "Hello ptr, Good morning"
True
*Main> 
*Main> isInfix [2, 3, 5] [1, 3, 5, 7, 2, 3, 5, 9]
True
*Main> 
*Main> isInfix [2, 3, 5] [1, 3, 5, 7, 2, 3, 9]
False
*Main> 
*Main> isInfix [] []
True
*Main> 
*Main> isInfix [] [2, 3, 5]
True
*Main> 


Previous                                                 Next                                                 Home

No comments:

Post a Comment