Hi John,
| 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)
As your experiments suggest, and contrary to what you've read, the
third version of fib does not run in constant space. For reference,
the code for version 3 is:
| f3 n = fibs !! n where
| fibs = 0:1:zipWith (+) fibs (tail fibs)
There are two reasons why this doesn't run in constant space:
- In the absence of a type declaration, the calculations will
default to using Integer arithmetic. Arbitrary precision
numbers cannot be represented in constant space.
- In the absence of strictness analysis or annotations, nothing
will force evaluation of the sum until the nth element has
been selected. The delayed representation of that sum will
not fit in constant space.
Try something like the following if you want to get round the
second problem:
f4 n = forceList fibs !! n where
fibs = 0:1:zipWith (+) fibs (tail fibs)
forceList (x:xs) = x `seq` (x:forceList xs)
forceList [] = []
All the best,
Mark
