Re: Why does this blow the stack?

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

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe