Proposal: Make a very slight change to the semantics of Data.List.isSuffixOf

[Jon Fairbairn]

David Feuer <david.feuer at gmail.com> writes:

> 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 at cl.cam.ac.uk
http://www.chaos.org.uk/~jf/Stuff-I-dont-want.html  (updated 2014-04-05)