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.