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

[Andreas Abel]

David, the essence of your idea seems mutually drop the correct number 
of elements from needle and hay and then compare for equality.  Here is 
a concise implementation of your idea in terms of drop:

isSuffixOf        :: forall a . (Eq a) => [a] -> [a] -> Bool
[] `isSuffixOf` _  =  True
xs `isSuffixOf` ys =  xs == drop (length (drop (length xs) ys)) ys

This can be further simplified to

isSuffixOf        :: forall a . (Eq a) => [a] -> [a] -> Bool
[] `isSuffixOf` _  =  True
xs `isSuffixOf` ys =  xs == drop (length ys - length xs) ys

which is a very easy to understand program, I think, without need to 
reverse lists.

On 10.10.2014 18:39, David Feuer wrote:
> I accidentally hit "send" before finishing this message. I *think* my
> version is probably a little easier to understand than Milan's but it
> also seems possible that Milan's could take the lead with some more
> inspired variable names. I also wish I knew a way to avoid the bogus
> pattern in skip_and_compare (and my equivalent), but I haven't been able
> to do so.
>
> On Oct 10, 2014 12:23 PM, "David Feuer" <david.feuer at gmail.com
> <mailto:david.feuer at gmail.com>> wrote:
>
>     I wouldn't say calling it on a possibly infinite list would
>     necessarily be the wisest thing, but supporting an infinite "needle"
>     with a finite "haystack" comes for free with the forward traversal.
>     Unlike inInfixOf, the extra implementation flexibility gained by
>     specifying that the needle is finite has no serious potential to
>     allow fancy algorithms to improve efficiency.
>
>     The real odd semantic duck, I think, is the special case for an
>     empty needle, because it is lazier than one might expect. In
>     particular, I would expect that isSuffixOf [] undefined would be
>     False, because undefined is not a []-terminated list. Leaving *that*
>     unspecified would make a lot of sense to me.
>
>     As for simplicity of form, orb__ came up with a version that uses
>     Either instead of Maybe to take advantage of the similarity of two
>     phases to get away with just one helper function, but I think that
>     approach is much harder to understand.
>
>     On Oct 10, 2014 10:48 AM, "John Lato" <jwlato at gmail.com
>     <mailto:jwlato at gmail.com>> wrote:
>
>         I think David's proposed definition is the easiest to read form
>         with good performance so far.
>
>         As to definedness, the change in semantics doesn't matter to
>         me.  But I think calling isSuffixOf on possibly infinite lists
>         is a bad idea anyway.
>
>         John L.
>
>         On Oct 10, 2014 5:35 AM, "Milan Straka" <fox at ucw.cz
>         <mailto:fox at ucw.cz>> wrote:
>          >
>          > Hi all,
>          >
>          > > -----Original message-----
>          > > From: David Feuer <david.feuer at gmail.com
>         <mailto: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 <mailto: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 <mailto:Libraries at haskell.org>
>          > http://www.haskell.org/mailman/listinfo/libraries
>
>
>         _______________________________________________
>         Libraries mailing list
>         Libraries at haskell.org <mailto:Libraries at haskell.org>
>         http://www.haskell.org/mailman/listinfo/libraries
>
>
>
> _______________________________________________
> Libraries mailing list
> Libraries at haskell.org
> http://www.haskell.org/mailman/listinfo/libraries
>


-- 
Andreas Abel  <><      Du bist der geliebte Mensch.

Department of Computer Science and Engineering
Chalmers and Gothenburg University, Sweden

andreas.abel at gu.se
http://www2.tcs.ifi.lmu.de/~abel/