{-
Thompson gives these 3 versions of fib, saying that the third is linear in
time, constant in space and the second is linear in both space and time.
(Thompson, 2nd edition, page 431)
for large values of n, I get a seg fault on version 3; that's certainly
not constant space. At least version 2 gives a stack overflow. This is
on Hugs98 September 1999 version on Windows (also May 1999 version), and
on Solaris May 1999 version.
John Atwood
-}
f1 0 = 0
f1 1 = 1
f1 n = f1 (n - 1) + f1 (n - 2)
f2 n = fst $ fP n
fP 0 = (0,1)
fP n = (y,x+y) where
(x,y) = fP (n - 1)
f3 n = fibs !! n where
fibs = 0:1:zipWith (+) fibs (tail fibs)
