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

[David Feuer]

On Fri, Oct 10, 2014 at 5:18 AM, Jon Fairbairn <jon.fairbairn at cl.cam.ac.uk>
wrote:

> That seems rather wordy to me. Can we get anywhere starting with
>
>
It is rather wordy; I just don't know how to do better.


>    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.
>

That looks bad. The implementation I gave is something like O(m+n), whereas
yours looks something like O(m*n).
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/libraries/attachments/20141010/42f4e970/attachment.html>