S. Alexander Jacobson <[EMAIL PROTECTED]> wrote
(sorry, i do not remember, to which of the Haskell lists)
> Wow! If Ralf is right, then foldl in a lazy language always generates
> a space leak and should be avoided in favor of strictFoldl.
> ...
There were other letters on foldl(Strict) and related things.
Concerning the un-needed laziness, we, probably, have to think about its
cost bound.
The evaluation cost is nR + C*nA,
where
nR is the number of "reduction steps",
nA number of the cell allocations (for new data).
C a constant depending on implementation.
- something like Time + Space.
And in the above example of foldl (+) 0 [1..b]
the ratio of the lazy evaluation cost to the strictness-optimised one
is
(b + C*b)/b = 1+C (1)
- a constant.
That is the strictness-optimised program costs near the same as the
naive.
If a naive program overflows memory space M, then the strictness-
optimised one will take at least as much time as C*M.
I suspect, (1) holds in general. How do you think?
------------------
Sergey Mechveliani
[EMAIL PROTECTED]
