[Haskell-cafe] (small) code review request

Radu Grigore radugrigore at gmail.com
Thu Jun 16 06:03:19 EDT 2005

On 6/16/05, Lennart Augustsson <lennart at augustsson.net> 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?


More information about the Haskell-Cafe mailing list