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

[David Feuer]

Sorry, I made a bit of a mistake with eq; it's corrected below.

On Wed, Oct 8, 2014 at 4:15 AM, David Feuer <david.feuer at gmail.com> wrote:

> Currently, isSuffixOf is defined like this:
>
> xs `isSuffixOf` ys = reverse xs `isPrefixOf` reverse ys
>
> If ys is much longer than xs, this is not so wonderful, because we have to
> reverse the whole spine of ys. It also will fail whenever either xs *or* ys
> is infinite. The following implementation seems a lot saner (although
> longer):
>
> isSuffixOf              :: forall a . (Eq a) => [a] -> [a] -> Bool
> []     `isSuffixOf` _   =  True
> needle `isSuffixOf` hay =
>       maybe False
>             (\fp -> needle `eq` getEndChunk hay fp)
>             (getFrontPointer needle hay)
>   where
>     eq :: [a] -> [a] -> Bool
>     (x:xs) `eq` (y:ys) = x==y && (xs `eq` ys)
>
        _         `eq` _        = True

>
>     getEndChunk :: [a] -> [a] -> [a]
>     getEndChunk (_:hy) (_:fp) = getEndChunk hy fp
>     getEndChunk hy     _      = hy
>
>     getFrontPointer :: [a] -> [a] -> Maybe [a]
>     getFrontPointer [] hy         = Just hy
>     getFrontPointer _  []         = Nothing
>     getFrontPointer (_:nd) (_:hy) = getFrontPointer nd hy
>
> This doesn't do any of that crazy stuff, and it will work just fine if the
> needle is infinite. The only slightly sticky point is that it's not
> *strictly* lazier. In particular,
>
> [1,2] `Data.List.isSuffixOf` [undefined, 7] = False
> [1,2] `isSuffixOf` [undefined, 7] = undefined
>
> But note that
>
> [1,2] `Data.List.isSuffixOf` [7,undefined] = undefined
> [1,2] `isSuffixOf` [7, undefined] = False
>
> It would be possible to get the same kind of laziness at the end using
> something structured as above, but it requires some unpleasantness: instead
> of using
>
> needle `eq` getEndChunk hay fp
>
> we'd have to use
>
> needle `backwardsEq` getEndChunk hay fp
>
> (x:xs) `backwardsEq` (y:ys) = (xs `backwardsEq` ys) && x==y
>
> This is yucky. My guess is that no one is relying on the current behavior,
> but I'd like to make sure everyone's okay with this.
>
> David
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/libraries/attachments/20141008/7d4ffef4/attachment.html>