[Haskell-cafe] (small) code review request

Lennart Augustsson lennart at augustsson.net
Thu Jun 16 11:33:25 EDT 2005


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


More information about the Haskell-Cafe mailing list