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

[David Feuer]

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> 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> 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/5aedeb07/attachment-0001.html>