[Haskell] Control.Monad.Writer as Python generator

[Jan-Willem Maessen]

On Apr 15, 2005, at 6:07 PM, ChrisK wrote:

>>> You are correct.  Moand.Cont yield even runs without -O optimizing,
>>> just slower
>>> ...
>>> Anyone have an idea why ghci can't garbage collect it?
>>> Is this an actual bug or an innate quirk of the REPL ?
>>
>> GHCi does not "compile" with optimizations, without -O the strictness 
>> analyzer
>> isn't run.
>
> The optimizer is irrelevant to whether it runs in constant space, as 
> ghc without '-O' runs it just fine.  The optimizer is only useful for 
> speed, which is not the issue.

Not true!  The optimizer can change the asymptotic space consumption of 
your program.  The example of sum is particularly germaine.  If we 
write:

x = foldl (+) 0 [1..n]

this will, as it is evaluated, generate the suspended computation
(((....((((0 + 1) + 2) + 3) + ...) + n

This require O(n) space.

Whereas the strict foldl' will evaluate each parenthesized expression 
as it is encountered:
(0+1) = 1
(1+2) = 3
(3+3) = 6
(6+4) = 10
...
(... + n) = your answer

If only we all used mostly-eager evaluation, these kinds of confusions 
would [almost] never happen.

-Jan-Willem Maessen
>