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