wren ng thornton wren at freegeek.org
Fri Sep 30 00:31:39 CEST 2011

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
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