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!!20))
main = print (show (nth 20 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 20 [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!!20)
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.
pgp0.pgp
Description: PGP signature
