Sorry, I made a bit of a mistake with eq; it's corrected below.
On Wed, Oct 8, 2014 at 4:15 AM, David Feuer
Currently, isSuffixOf is defined like this:
xs `isSuffixOf` ys = reverse xs `isPrefixOf` reverse ys
If ys is much longer than xs, this is not so wonderful, because we have to reverse the whole spine of ys. It also will fail whenever either xs *or* ys is infinite. The following implementation seems a lot saner (although longer):
isSuffixOf :: forall a . (Eq a) => [a] -> [a] -> Bool [] `isSuffixOf` _ = True needle `isSuffixOf` hay = maybe False (\fp -> needle `eq` getEndChunk hay fp) (getFrontPointer needle hay) where eq :: [a] -> [a] -> Bool (x:xs) `eq` (y:ys) = x==y && (xs `eq` ys)
_ `eq` _ = True
getEndChunk :: [a] -> [a] -> [a] getEndChunk (_:hy) (_:fp) = getEndChunk hy fp getEndChunk hy _ = hy
getFrontPointer :: [a] -> [a] -> Maybe [a] getFrontPointer [] hy = Just hy getFrontPointer _ [] = Nothing getFrontPointer (_:nd) (_:hy) = getFrontPointer nd hy
This doesn't do any of that crazy stuff, and it will work just fine if the needle is infinite. The only slightly sticky point is that it's not *strictly* lazier. In particular,
[1,2] `Data.List.isSuffixOf` [undefined, 7] = False [1,2] `isSuffixOf` [undefined, 7] = undefined
But note that
[1,2] `Data.List.isSuffixOf` [7,undefined] = undefined [1,2] `isSuffixOf` [7, undefined] = False
It would be possible to get the same kind of laziness at the end using something structured as above, but it requires some unpleasantness: instead of using
needle `eq` getEndChunk hay fp
we'd have to use
needle `backwardsEq` getEndChunk hay fp
(x:xs) `backwardsEq` (y:ys) = (xs `backwardsEq` ys) && x==y
This is yucky. My guess is that no one is relying on the current behavior, but I'd like to make sure everyone's okay with this.
David