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

[Jules Bean]

David House wrote:
> On 16/05/07, Sergey Perminov <sv.perminov at gmail.com> 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