[Haskell-cafe] Why does this blow the stack?
Don Stewart
dons at galois.com
Fri Dec 21 15:02:31 EST 2007
coeus:
> 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.
>
There's no good reason for the accumulator for Integer to be lazy,
especially when you see that adding an upper bound (enumFromTo) or
using Int uses a strict accumulator.
I've filled a bug report and fix for this.
http://hackage.haskell.org/trac/ghc/ticket/1997
there's an ad hoc sprinkling of strict and lazy Num ops for Integer
through the base library, while Int is fairly consistently strict.
-- Don
More information about the Haskell-Cafe
mailing list