View source for Stack overflow

== Scans ==

A subtle stack-overflow surprise comes when
<haskell>
print (scanl (+) 0 [1..1000000])
</haskell>
completes successfully but
<haskell>
print (last (scanl (+) 0 [1..1000000]))
</haskell>
causes a stack overflow.

The latter stack overflow is explained exactly as before, namely,
<haskell>
last (scanl (+) 0 [1..5]) ->
... several steps ... ->
((((0+1)+2)+3)+4)+5
</haskell>
This is exactly like <hask>foldl</hask>, building a deep thunk, then evaluating, needing much stack.

Most puzzling is why the former succeeds without a stack overflow. This is caused by a combination of two factors:
* thunks in the list produced by <hask>scanl</hask> enjoy sharing: late thunks build upon early thunks
* printing a list of numbers evaluates early thunks and then late thunks
To exemplify, here is an abridged progression. I use this pseudo format to depict sharing of thunks
<haskell>
expr where var=expr, var=expr
</haskell>
although in reality it is more like a pointer graph.
<haskell>
print (scanl (+) 0 [1..1000000]) ->
print (a : case [1..1000000] of <nowiki>...</nowiki> x:xs -> scanl (+) (a+x) xs) where a=0 ->
<nowiki>... evaluate a to 0 for printing, I/O, some more steps ...</nowiki> ->

print (scanl (+) (a+1) [2..1000000]) where a=0 ->
print (b : case [2..1000000] of <nowiki>...</nowiki> x:xs -> scanl (+) (b+x) xs) where a=0, b=a+1 ->
<nowiki>... evaluate b to 1 for printing, I/O, some more steps ...</nowiki> ->

print (scanl (+) (b+2) [3..1000000]) where b=1 ->
print (c : case [3..1000000] of <nowiki>...</nowiki> x:xs -> scanl (+) (c+x) xs) where b=1, c=b+2 ->
<nowiki>... evaluate c to 3 for printing, I/O, some more steps ...</nowiki> ->

print (scanl (+) (c+3) [4..1000000]) where c=3 ->
print (d : case [4..1000000] of <nowiki>...</nowiki> x:xs -> scanl (+) (d+x) xs) where c=3, d=c+3 ->
<nowiki>... evaluate d to 6 for printing, I/O, some more steps ...</nowiki> ->

print (scanl (+) (d+4) [5..1000000]) where d=6 -> etc.
</haskell>
The important thing to watch is the life cycle of intermediate thunks, e.g., <hask>c</hask> is created at some point as a 1-level deep addition, then almost immediately reduced to a number out of necessity, before a later thunk <hask>d</hask> builds upon it. Therefore there is no growth and no stack overflow.

In contrast, again, <hask>last (scanl (+) 0 [1..1000000])</hask> skips over to the last thunk right away. Since early items are not reduced yet, the last item remains a huge chain and causes overflow.

As an addendum, there are three ways of handling this problem and similar ones:
# You can have your traversal functions (in this case, last) force the list as it goes along.
# You can use (perhaps custom) versions of the list (or data structure, in general) producing functions (in this case, scanl) that force the elements as it builds the data structure.
# You can use a data structure that's strict in its elements, in this case it would be a head strict list.