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

11 Oct 2014

      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" mailto:david.feuer@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" mailto:jwlato@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" mailto:fox@ucw.cz> wrote:
         >
         > Hi all,
         >
         > > -----Original message-----
         > > From: David Feuer mailto:david.feuer@gmail.com>
         > > Sent: 10 Oct 2014, 05:23
         > >
         > > On Fri, Oct 10, 2014 at 5:18 AM, Jon Fairbairn
        mailto: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 mailto:Libraries@haskell.org
         > http://www.haskell.org/mailman/listinfo/libraries
_______________________________________________
        Libraries mailing list
        Libraries@haskell.org mailto:Libraries@haskell.org
        http://www.haskell.org/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
Libraries@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@gu.se
http://www2.tcs.ifi.lmu.de/~abel/