Proposal: Make a very slight change to the semantics of Data.List.isSuffixOf
Jon Fairbairn
jon.fairbairn at cl.cam.ac.uk
Fri Oct 10 09:18:14 UTC 2014
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)
More information about the Libraries
mailing list