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

[Don Stewart]

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