Re[Haskell-cafe] [2]: Re[2]: Reduction Sequence of simple Fibonacci sequence implementation

[Ketil Malde]

staafmeister <g.c.stavenga at uu.nl> writes:

> The list you give prod is also 10 MB so it not a terribly
> inefficient program.  It's a factor of 2.

No, it is not.  The expression:

  prod [1..1000] + sum [1..1000] 

will first evaluate prod [1..1000], generating values from 1 to 1000
lazily and accumulating the product incrementally, allowing the used
values to be GC'ed.  Then the sum will be evaluated similarly, and the
two results will be added.  It will run in constant - and very small
space. 

If you do common sub-expression elimination (CSE), and write

   let ls = [1..1000] in prod ls + sum ls

the product will force ls to be evaluated, but since there is another
reference to this value (for the sum), it cannot be garbage collected.

Thus, the difference is more like a factor of 1000, which is a big
deal. 

-k
-- 
If I haven't seen further, it is by standing in the footprints of giants