David Feuer
A slight simplification (because I realized the weird thing I was doing won't actually save any time):
isSuffixOf :: forall a . (Eq a) => [a] -> [a] -> Bool [] `isSuffixOf` _ = True needle `isSuffixOf` hay = maybe False (\fp -> needle == getEndChunk hay fp) (getFrontPointer needle hay) where 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
That seems rather wordy to me. Can we get anywhere starting with a `isSuffixOf` b = a `elem` tails b and transforming? I’m not awake enough to the efficiency implications, but a `isSuffixOf` b = a `elem` (take 1 $ dropWhile (longerThan a) $ tails b) longerThan _ [] = False longerThan [] _ = True longerThan (_:a) (_:b) = longerThan a b looks plausible.
I still haven't heard from anyone about the slight semantic change. To clarify it slightly, the only aspect that could theoretically be a problem for somebody is that this reverses the order in which the elements of the "needle" are compared to the (length needle) elements at the end of the "haystack". The current implementation compares them from back to front; this one compares them from front to back. That means that if some elements in the needle or near the end of the haystack are undefined, there are cases where this implementation bottoms out when the current one returns False, and vice versa.
This doesn’t bother me. Comparing forwards seems more a “natural” expectation. -- Jón Fairbairn Jon.Fairbairn@cl.cam.ac.uk http://www.chaos.org.uk/~jf/Stuff-I-dont-want.html (updated 2014-04-05)