<p dir="ltr">A slight simplification (because I realized the weird thing I was doing won't actually save any time):</p>
<p dir="ltr">isSuffixOf :: forall a . (Eq a) => [a] -> [a] -> Bool<br>
[] `isSuffixOf` _ = True<br>
needle `isSuffixOf` hay =<br>
maybe False<br>
(\fp -> needle == getEndChunk hay fp)<br>
(getFrontPointer needle hay)<br>
where<br>
getEndChunk :: [a] -> [a] -> [a]<br>
getEndChunk (_:hy) (_:fp) = getEndChunk hy fp<br>
getEndChunk hy _ = hy</p>
<p dir="ltr"> getFrontPointer :: [a] -> [a] -> Maybe [a]<br>
getFrontPointer [] hy = Just hy<br>
getFrontPointer _ [] = Nothing<br>
getFrontPointer (_:nd) (_:hy) = getFrontPointer nd hy</p>
<p dir="ltr">I still haven't heard from anyone about the slight semantic change. To clarify it slightly, the only aspect that could theoretically be a problem for somebody is that this reverses the order in which the elements of the "needle" are compared to the (length needle) elements at the end of the "haystack". The current implementation compares them from back to front; this one compares them from front to back. That means that if some elements in the needle or near the end of the haystack are undefined, there are cases where this implementation bottoms out when the current one returns False, and vice versa.</p>
<div class="gmail_quote">On Oct 8, 2014 4:17 AM, "David Feuer" <<a href="mailto:david.feuer@gmail.com">david.feuer@gmail.com</a>> wrote:<br type="attribution"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Sorry, I made a bit of a mistake with eq; it's corrected below.<br><div><div class="gmail_extra"><br><div class="gmail_quote">On Wed, Oct 8, 2014 at 4:15 AM, David Feuer <span dir="ltr"><<a href="mailto:david.feuer@gmail.com" target="_blank">david.feuer@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div><div><div><div><div><div><div><div><span style="font-family:arial,helvetica,sans-serif">Currently, isSuffixOf is defined like this:<br><br>xs `isSuffixOf` ys = reverse xs `isPrefixOf` reverse ys<br><br>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):<br><br>isSuffixOf :: forall a . (Eq a) => [a] -> [a] -> Bool<br>[] `isSuffixOf` _ = True<br>needle `isSuffixOf` hay =<br> maybe False<br> (\fp -> needle `eq` getEndChunk hay fp)<br> (getFrontPointer needle hay)<br> where<br></span></div><div><span style="font-family:arial,helvetica,sans-serif"> eq :: [a] -> [a] -> Bool<br></span></div><div><span style="font-family:arial,helvetica,sans-serif"> (x:xs) `eq` (y:ys) = x==y && (xs `eq` ys)<br></span></div></div></div></div></div></div></div></div></div></blockquote><div> _ `eq` _ = True <br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div><div><div><div><div><div><div><div><span style="font-family:arial,helvetica,sans-serif"><br></span></div><div><span style="font-family:arial,helvetica,sans-serif"> getEndChunk :: [a] -> [a] -> [a]<br></span></div><div><span style="font-family:arial,helvetica,sans-serif"> getEndChunk (_:hy) (_:fp) = getEndChunk hy fp<br> getEndChunk hy _ = hy<br><br> getFrontPointer :: [a] -> [a] -> Maybe [a]<br> getFrontPointer [] hy = Just hy<br> getFrontPointer _ [] = Nothing<br> getFrontPointer (_:nd) (_:hy) = getFrontPointer nd hy<span></span><span></span><br><br>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,<br><br></span></div><span style="font-family:arial,helvetica,sans-serif">[1,2] `Data.List.isSuffixOf` [undefined, 7] = False<br></span></div><span style="font-family:arial,helvetica,sans-serif">[1,2] `isSuffixOf` [undefined, 7] = undefined<br><br></span></div><span style="font-family:arial,helvetica,sans-serif">But note that<br><br></span></div><span style="font-family:arial,helvetica,sans-serif">[1,2] `Data.List.isSuffixOf` [7,undefined] = undefined<br></span></div><span style="font-family:arial,helvetica,sans-serif">[1,2] `isSuffixOf` [7, undefined] = False<br><br></span></div><span style="font-family:arial,helvetica,sans-serif">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<br><br>needle `eq` getEndChunk hay fp<br><br></span></div><span style="font-family:arial,helvetica,sans-serif">we'd have to use<br><br>needle `backwardsEq` getEndChunk hay fp<br><br>(x:xs) `backwardsEq` (y:ys) = (xs `backwardsEq` ys) && x==y<br><br></span></div><div><span style="font-family:arial,helvetica,sans-serif">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.<span><font color="#888888"><br><br></font></span></span></div><span><font color="#888888"><div><span style="font-family:arial,helvetica,sans-serif">David<br></span></div></font></span></div>
</blockquote></div><br></div></div></div>
</blockquote></div>