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 I assume this is not in Data.List to discourage people from doing things to the right side of lists... it's still useful for string stuff where ByteString would be overkill though.

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) []

David House wrote:

On 16/05/07, Sergey Perminov wrote:

...

How to solve task of reversing big list with constant heap space used?

I think that as lists are singly-linked in Haskell, reversing a list will always be O(n) space.

You can do it in O(n^2) time and constant space, by using repeated calls to (!!), in principle. In practice you need to be a bit tricky otherwise keeping the reference to the whole list around will stop the GC ever collecting it. You'd need to stream it rather carefully, and then it wouldn't actually be (!!) any more; just something 'like (!!)'. Jules