[Haskell-cafe] (small) code review request

[Lennart Augustsson]

Radu Grigore wrote:
> Anyway, I was wondering if the O(n) space and O(n^2) time solution can
> be implemented in Haskell. Another way to ask this. Consider the
> classic fibonacci example. Can one compute the n-th fibonacci number
> in O(n) time and O(1) space, i.e. remember only the "last" two values
> during computation?

Assuming an O(1) + operation you can do

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

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)

	-- Lennart