[Haskell-cafe] reversing big list with constant heap space used

[Henning Thielemann]

On Wed, 16 May 2007, Evan Laforge wrote:

> > I think that in every particular case you have to find out how to avoid
> > 'reverse'. Especially if you have two 'reverse's like in
> >    reverse . dropWhile p . reverse
> >  there are more efficient solutions.
>
> Just from curiosity, what *is* an efficient way to do rDropWhile?
> Here's something which at least avoids 2 reverses:
>
> rDropWhile = doRDropWhile []
>
> doRDropWhile accum f [] = []
> doRDropWhile accum f (x:xs)
>     | f x = doRDropWhile (x:accum) f xs
>     | otherwise = reverse (x:accum) ++ doRDropWhile [] f xs


http://www.haskell.org/pipermail/libraries/2005-August/004217.html

dropWhileRev :: (a -> Bool) -> [a] -> [a]
dropWhileRev p =
   foldr (\x xs -> if p x && null xs then [] else x:xs) []