On 06/01/2007, at 12:58 PM, Jeremy Shaw wrote:
Because you never demand the value of any element in the list, Haskell never bothers to calculate it. So you have a list that looks like:
[ i, i - 1, (i - 1) - 1, ((i - 1) - 1 - 1), .. ]
So, by the time you get up to some big numbers, you have built up a very large thunk. For some reason this is causing a stack overflow.
Right. And to clarify, the reason is that the thunk is one big chain of applications of (-). Imagine what will happen when the topmost application is evaluated. Because (-) is strict in its arguments they must be evaluated before the minus can proceed. So the left and right arguments are evaluated. The left argument is itself an application of (-) and so on. The whole left branch eventually gets pushed onto the stack. Because the left branch is so long, the stack eventually overflows. This is one of those examples where optimistic evaluation would be a win. Cheers, Bernie.