Re: [Haskell-cafe] (small) code review request

On 6/16/05, Lennart Augustsson wrote:

fib n = f n 1 1 where f 0 _ b = b f n a b = f (n-1) (a+b) a

Indeed. I should have seen this. It's a pretty standard trick for making a function tail recursive.

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? -- regards, radu http://rgrig.blogspot.com/