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

Ketil Malde ketil at
Fri Aug 28 08:09:36 EDT 2009

staafmeister <g.c.stavenga at> 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

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

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

More information about the Haskell-Cafe mailing list