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

12 Oct 2014

      Well, you also traverse the haystack twice, in your getEndChunk function 
you simultaneously traverse the haystack and a (shared) copy of it.  Why 
is this so much better?

I guess without data (timings, heap-profiles) we do not get further here.

On 11.10.2014 14:47, David Feuer wrote:
...
It can be, but your way traverses the entire haystack *twice*. The
memory needs are equivalent to the reversing version, which I consider
unacceptable.
I do not understand this comment.  reverse needs O(n) memory, length O(1).

Cheers,
Andreas
...
On Sat, Oct 11, 2014 at 5:57 AM, Andreas Abel mailto:abela@chalmers.se> wrote:
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.
_______________________________________________
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/