[Haskell-cafe] reversing big list with constant heap space used
jules at jellybean.co.uk
Wed May 16 16:47:06 EDT 2007
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 (!!)'.
More information about the Haskell-Cafe