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

[apfelmus]

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

How about a fold?

  rDropWhile f = either (const []) id . foldr g (Left ())
    where
    g x (Left  _ ) = if f x then Left () else Right [x]
    g x (Right xs) = Right (x: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.

Indeed, the list data structure is intended to be used from the left
only. For double-end access, there are queues and Data.Sequence.

Regards,
apfelmus