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

Don Stewart dons at galois.com
Fri Dec 21 15:02:31 EST 2007

> 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.


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