Re: [Haskell-cafe] Type systems preventing laziness-related memory leaks?

On Fri Feb 20 2015 at 1:23:25 AM Roman Cheplyaka wrote:

On 20/02/15 07:26, Eugene Kirpichov wrote:

...

On Tue Feb 17 2015 at 11:50:20 PM Roman Cheplyaka mailto:roma@ro-che.info> wrote:

Note that foldr (+) 0 has nothing to do with laziness — it's eager.

Its

...

problem is that it's not tail-recursive.

The problem is that when you say foldr (+) 0 [1, 2, 3, 4, 5] you build a thunk "1 + (2 + (3 + (4 + (5 + 0))))", which has - let's call it "whnf evaluation depth" of 4 (you need a stack of size 4 to evaluate it to

whnf).

This is not a thunk. These values would be pushed to the stack, but no thunks will be created.

Just so that you have no doubts left, here's the STG code for foldr (+) 0:

$wgo = \r srt:SRT:[] [w] case w of _ { [] -> 0; : y ys -> case y of _ { I# x -> case $wgo ys of ww { __DEFAULT -> +# [x ww]; }; }; };

As you can see, there are no lets here, only cases.

Indeed - I guess the strictness analyzer did its job. Nevertheless, the expression foldr (+) 0 [1..n] requires an evaluation stack depth of n and I would like it to be uncompilable - I would like the type of foldr (+) 0 to be "[Int] -> Int@\infty"

Roman