David House wrote:
On 16/05/07, Sergey Perminov <[EMAIL PROTECTED]> 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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
