Proposal: adding 'tailDropWhile' to Data.List

[wren ng thornton]

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