Radu Grigore wrote:
List based solutions should also work if garbage collection is done right, e.g., fib n = fs !! n where fs = 1 : 1 : zipWith (+) fs (tail fs)
So you mean my solution of the LCS problem should work in O(n) space "if garbage collection is done right"? What exactly does this condition mean in practice?
Well, for fib I'd say that almost any implementation manages to garbage collect the part of the list that is no longer needed. But in this example the difficult part is that (+) operation isn't typically performed until the (!!) has returned the value. I say typically, because a clever strictness analyzer might get it right. And so can a modestly clever garbage collector, it can collapse the (+) operations. As far as I know, no currently available implementations do this. :( To make this fib function run in constant space you need to make it a little stricter. In cases like these, the heap profiler is your friend. It can show you where memory is leaking. -- Lennart