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

[David Feuer]

I did another set of benchmarks, and Milan's implementation has a small but
clear advantage over mine. Therefore I amend my proposal to use Milan's
implementation instead. I would suggest perhaps using the following names:

isSuffixOf :: (Eq a) => [a] -> [a] -> Bool
[] `isSuffixOf` _ = True
needle `isSuffixOf` hay = dropNeedleFromHay needle hay
  where dropNeedleFromHay [] remainingHay = dropToHayEnd remainingHay hay
        dropNeedleFromHay _  []           = False -- needle longer than hay
        dropNeedleFromHay (n:ns) (h:hs)   = dropNeedleFromHay ns hs

        dropToHayEnd [] suffix = needle == suffix
        dropToHayEnd _ [] = True -- This can't happen, but returning True
is measurably (slightly) faster than throwing an error here.
        dropToHayEnd (d:ds) (s:ss) = dropToHayEnd ds ss

On Fri, Oct 10, 2014 at 8:34 AM, Milan Straka <fox at ucw.cz> wrote:

> Hi all,
>
> > -----Original message-----
> > From: David Feuer <david.feuer at gmail.com>
> > Sent: 10 Oct 2014, 05:23
> >
> > 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.
>
> What about something like the following? It uses exactly the same
> algorithm, it just avoids the maybe combinator and Maybe internal
> result, and renames stuff:
>
> isSuffixOf :: (Eq a) => [a] -> [a] -> Bool
> [] `isSuffixOf` _ = True
> needle `isSuffixOf` hay = subtract_and_compare needle hay
>   where subtract_and_compare [] diff = skip_and_compare diff hay
>         subtract_and_compare _ [] = False -- needle longer than hay
>         subtract_and_compare (n:ns) (h:hs) = subtract_and_compare ns hs
>
>         skip_and_compare [] suffix = needle == suffix
>         skip_and_compare _ [] = True -- first argument must also be []
>         skip_and_compare (d:ds) (s:ss) = skip_and_compare ds ss
>
> The redundant skip_and_compare case is there just for completeness and
> readability.
>
> Cheers,
> Milan
> _______________________________________________
> Libraries mailing list
> Libraries at haskell.org
> http://www.haskell.org/mailman/listinfo/libraries
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/libraries/attachments/20141013/16c003ca/attachment.html>