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

[Andreas Abel]

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 <abela at chalmers.se
> <mailto:abela at 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 at 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 at gu.se
http://www2.tcs.ifi.lmu.de/~abel/