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

[David Feuer]

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] -> [a]
    (x:xs) `eq` (y:ys) = x==y && (xs `eq` ys)

    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/f57e8f7a/attachment.html>