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

[David Feuer]

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> 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> 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
>
> _______________________________________________
> 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/20141010/696e1eb9/attachment.html>