On the evil iteration laziness. Do not panic.
---------------------------------------------
There were a couple of messages from me on the subject of the evil
treating of iteration in lazy evaluation. The worst examples are
like this:
let sum xs = foldl (+) 0 xs ::Int in sum [1..n]
Probably, in most Haskellish systems `sum' is implemented this way.
And this causes a strangely large need for the stack/heap space -
proportional to n - as if the list [1..n] was not lazy.
This is due to that the lazy `foldl' generates here the expessions
like
foldl (+) (..(+(+(+ 0 1) 2) 3)..) [4..]
That is the lazy evaluation of sub-expression sometimes cause the
evil strictness effect in the whole iteration process. And this is
why the popular recursion-to-iteration technique may yield the bad
performance.
I hope the Haskellites have not yet got into such a panic as to whipe
out all their programs. The situation is not so tragically bad.
For example, the iterations
foldl (+) zeroPolynomial [x^i | i<-[0..n]] (1)
reverse xs = foldl (\ys x->x:ys) [] xs
are quite good.
Because in (1), (+) accumulates the linearly increasing in size sum
1 + x + x^2 + x^3 + ... - the result is as large as xs.
The same is with `reverse'.
Another observation is that on average, xs is still unfolded only
half-lazily. For the other parts of the embracing program may use the
same variable xs, and as they unfold xs, its values are re-used in
this iteration, and it still have to take that much space.
The in-formal summary:
the effect of the evil lazy iteration with the "accumulating
function" f and the "argument list" xs takes place when
(EI):
(f z x) increases the "sum" z slowly and
xs is unfolded slowly by the other parts of computation.
So, the worst example might be, say: foldl min 0 [1..n] :: Int
Probably, in such evil iteration case, we have to apply `strict' and
provide foldl_new to do this on the generic basis:
------------------------------------------------------------------
sum xs = foldl_new Strict (+) 0 xs
foldl_new :: Eval a=> StrictnessFlag -> (a->b->a) -> a -> [b] -> a
foldl_new Lazy = foldl
foldl_new _ = foldl_s
where
foldl_s _ z [] = z
foldl_s f z (x:xs) = strict (\u->foldl_s f u xs) (f z x)
data StrictnessFlag = Lazy | Strict
- ?
------------------------------------------------------------------
Personally, I hate this `strict' thing.
The best solution might be the clever compiler that seeing the final
usage (and type) of (+) satisfying the condition (EI), creates the
"internal" specialization of sum xs to foldl_new Strict (+) 0 xs.
In its generic setting, such a detection task is algorithmically
un-solvable. Still this is, probably, a good subject for the program
transformators. For they might try to solve it for the large range
of simple cases.
It may well occur, the functional tool designers are aware of all this
(by the way, what does the `strictness analyzer'?) and are inventing
the corresponding tools.
In this case, the example with sum xs :: Int, shows that the task
is far too hard ...
------------------
Sergey Mechveliani
[EMAIL PROTECTED]
