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

13 Oct 2014


      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  wrote:
...
Hi all,
...
-----Original message-----
From: David Feuer 
Sent: 10 Oct 2014, 05:23
On Fri, Oct 10, 2014 at 5:18 AM, Jon Fairbairn <
jon.fairbairn@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@haskell.org
http://www.haskell.org/mailman/listinfo/libraries