On 9/28/11 10:06 AM, Ben Millwood wrote:
I'd implement it as:
tailDropWhile :: (a -> Bool) -> [a] -> [a] tailDropWhile p xs = go id xs where go _ [] = [] go k (x:xs) | p x = go (k . (x:)) xs | otherwise = k (x : go id xs)
which is as lazy as possible and doesn't involve any reversing.
The reversing isn't the problematic part. Since GHC.List defines reverse xs = rev xs [], the problematic bit is the concatenation. Rather than writing (reverse xs ++ ys) which is (rev xs [] ++ ys), what we really want is (rev xs ys) so that we don't need to traverse the results of rev in order to copy them onto the front of ys. And this is exactly the fusion you've done when converting to difference-list style. The version I provided in the previous thread was aimed mainly at being clear about the fact that it's just a PDA (since the thread was asking about how we could possibly define such a function). As I recall, I mentioned using difference lists as one of the many ways of optimizing the version I presented. Another of the optimizations I mentioned is that you can optimize away the need to keep track of the machine's state, since it's so simple; as you demonstrate, you only really need a single state (and the stack/continuation). The good-producer version with difference lists is straightforward: tailDropWhile p = \xs0 -> build (builder xs0) where builder xs0 cons nil = go id xs0 where go _ [] = nil go k (x:xs) | p x = go (k . cons x) xs | otherwise = k (x `cons` go id xs) -- Live well, ~wren