Fwd: [Haskell-cafe] Re: curious about sum
However it does not work as I expected. I ´m interested in memory
management.
I though that
ghci> let l= [1..1000000]
ghci> foldl' (+) 0 l
would produce a stack overflow, since the list can not be freed, because l
points to the beginning of the list
however it succeed
My conclussion is that, in the case of sum, with the lazy evaluation, isn´t
the list what is the cause of the stack overflow, but the lazy structure
0 + 1 +2 + 3 +4....
created by foldl before the final evaluation
I tried to test how I can force a stack overflow, in the strict case. Since
foldl' is strict, the only way is to create a long long initial list.
ghci> let l= [1..100000000] -- 100 times larger, two 0's added
ghci> foldl' (+) 0 l
as in the previous case, l will not garbage collect, and foldl' must build
the real list [1,2,3,4..] . at the end perhaps a stack overflow willl be
produced
This is not the case in my windows system.ghc 6.10.1. instead of that,
ghci grow to gigabyte size and more. I stopped the process or my machine
would be irresponsive.
My question is: Why the process does not grow also in the lazy case and
instead produces a stack overflow inmediately?
Yes I know that all of this is bizantine since strictness analysis would
solve this when compiled, but I think that there are somethig that i don´t
understand.
It´s a bug perhaps???
2009/6/18 Edward Kmett
On Thu, Jun 18, 2009 at 9:14 AM, Gleb Alexeyev
wrote: Thomas Davie wrote:
No, I think it's extremely useful. It highlights that numbers can both be lazy and strict, and that the so called "useless" lazy sum, is in fact, useful.
But lazy sum should have beed defined in terms of foldr, not foldl. And foldl is not strict enough for strict sum. Therefore the current choice in the worst of both worlds.
I definitely agree with that sentiment.
-Edward Kmett
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
On Thu, Jun 18, 2009 at 6:38 PM, Alberto G. Corona
My question is: Why the process does not grow also in the lazy case and instead produces a stack overflow inmediately?
This question is answered in detail on the Wiki http://www.haskell.org/haskellwiki/Foldr_Foldl_Foldl%27 As you thought, it is not the evaluation of foldl that overflow the stack, since foldl is terminally recursive it won't ever overflow the stack. On the other hand when the thunk created by foldl is finally evaluated, if the argument function is strict in its first argument it will overflow the stack if the list was too long. It is important to note that the size of the list itself or even the thunk doesn't guarantee a stack overflow : both of those structure are in the heap and if the argument function can produce output before evaluating its first argument, there will be no stack overflow, whatever the size of the thunk. As evidenced by this expression : ghci> take 10 . foldl (flip (:)) [] $ [1..1000000] [1000000,999999,999998,999997,999996,999995,999994,999993,999992,999991] -- Jedaï
Very informative. The list is in the heap but the lazy sum of foldl is in
the stack. ok.I suppose that all tail recursive functions are detected by
the strictness analysis.
2009/6/18 Chaddaï Fouché
On Thu, Jun 18, 2009 at 6:38 PM, Alberto G. Corona
wrote: My question is: Why the process does not grow aleso in the lazy case and instead produces a stack overflow inmediately?
This question is answered in detail on the Wiki http://www.haskell.org/haskellwiki/Foldr_Foldl_Foldl%27 As you thought, it is not the evaluation of foldl that overflow the stack, since foldl is terminally recursive it won't ever overflow the stack. On the other hand when the thunk created by foldl is finally evaluated, if the argument function is strict in its first argument it will overflow the stack if the list was too long.
It is important to note that the size of the list itself or even the thunk doesn't guarantee a stack overflow : both of those structure are in the heap and if the argument function can produce output before evaluating its first argument, there will be no stack overflow, whatever the size of the thunk.
As evidenced by this expression : ghci> take 10 . foldl (flip (:)) [] $ [1..1000000] [1000000,999999,999998,999997,999996,999995,999994,999993,999992,999991]
-- Jedaï
participants (2)
-
Alberto G. Corona -
Chaddaï Fouché