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
signature.asc
Description: This is a digitally signed message part.
_______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
