[Haskell-cafe] Why does this blow the stack?

[Marc A. Ziegert]

Am Freitag, 21. Dezember 2007 schrieb Justin Bailey:
> Given this function:
> 
>   dropTest n = head . drop n $ [1..]
> 
> I get a stack overflow when n is greater than ~ 550,000 . Is that
> inevitable behavior for large n? Is there a better way to do it?
> 
> Justin

[1..] equals [1, (1)+1, (1+1)+1, (1+1+1)+1, (1+1+1+1)+1, ...] where the brackets are a reference to the previous entry in the list.
so, if you want to reach the nth element in [1..], then the garbage collector automagically collects the unused list entries... but there are no unused.

[1..]!!10 = ((((((((((1)+1)+1)+1)+1)+1)+1)+1)+1)+1)+1
now, that one long formula needs to be completely build in the stack prior to evaluation.
to prevent this, each value has to be evaluated before stepping deeper into the list. i.e. like with this bang pattern:

let ((!x):xs)!!!i = case i of {0->x;_->xs!!!pred i} in [1..]!!!10

or simply like this trick:
[1..maxBound]!!10
this causes every single entry to be checked against the list-end-condition, just before the calculation of the next list entry.


- marc

-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: This is a digitally signed message part.
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20071221/2b4b8d14/attachment.bin