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

[Kim-Ee Yeoh]

On Fri, Oct 10, 2014 at 4:18 PM, Jon Fairbairn <jon.fairbairn at cl.cam.ac.uk>
wrote:

> That seems rather wordy to me. Can we get anywhere starting with
>
>    a `isSuffixOf` b = a `elem` tails b
>
> and transforming?


Is it only about wordiness & syntax?

With the original

    a `isSuffixOf` b = reverse a `isPrefixOf` reverse b

and with Jon's

    a `isSuffixOf` b = a `elem` tails b

I'm completely convinced of the correctness, modulo that of the referenced
functions. Moreover, the conviction was obtained cheaply. My finite neurons
are saved for the greater task at hand.

The proposal on the table snatches away that providence. I have to take it
on the authority of others that it's correct.

Rust recently exposed a bug in their string matching function. It's their
version of Data.List.isInfixOf. See

http://www.wabbo.org/blog/2014/22aug_on_bananas.html

These days I point all my colleagues and friends to this article as a
classic case of premature optimization. But I understand that some folks
prefer their computations always rapid, if sometimes wrong.

David, is there an application underlying the need for isSuffixOf speed?
You might want to look into the ByteString libraries for your optimization
efforts. Over there, performance is several notches up in priority.

-- Kim-Ee
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/libraries/attachments/20141011/041c122f/attachment.html>