Re[Haskell-cafe] [2]: Re[2]: Reduction Sequence of simple
Fibonacci sequence implementation
Ketil Malde
ketil at malde.org
Fri Aug 28 08:09:36 EDT 2009
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
More information about the Haskell-Cafe
mailing list