Hi Serguey! On Tue, Aug 19, 2003 at 03:14:53PM -0700, Serguey Zefirov wrote: > Hello glasgow-haskell-users, > > The following program > ----------------------------------------------- > --main = print (show (fibs!!200000)) > main = print (show (nth 200000 fibs)) > > nth 0 (h:_) = h > nth n (h:t) = nth (n-1) t > > fibs :: [Integer] > -- fibs = 1 : (map snd $ iterate (\(x,y) -> (y, x+y)) (1,1)) > fibs = [1..] > ----------------------------------------------- > compiled with ghc 6.0: > > ghc -O -o a.exe a.hs > > does not execute correctly. It causes stack overflow in 1M stack. > > If we change "fibs :: [Integer]" to "fibs :: [Int]" the new program > runs Ok.
I was confused by that at first, too. This is caused by the way [1..] works. `nth 200000 [1..]' returns the expression `1+1+1+1+1+1+1+...+1' and evaluating that causes the stack overflow. For Ints the additions are apparently carried out during the construction of [1..], probably because they are considered cheap. You can fix this by using === elementStrict :: [a] -> [a] elementStrict = foldr (($!) (:)) [] === and replacing [1..] by (elementStrict [1..]). With that, the following program will also work. === module Main(main) where main = print (fibs!!200000) fibs :: [Integer] fibs = 1 : elementStrict (map snd $ iterate (\(x,y) -> (y, x+y)) (1,1)) === It produces a result with 41798 decimal digits. Greetings, Carsten -- Carsten Schultz (2:40, 33:47), FB Mathematik, FU Berlin http://carsten.fu-mathe-team.de/ PGP/GPG key on the pgp.net key servers, fingerprint on my home page.
pgp00000.pgp
Description: PGP signature
