What's difference between Integer and Int?

[Carsten Schultz]

--O5XBE6gyVG5Rl6Rj
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable

Hi Serguey!

On Tue, Aug 19, 2003 at 03:14:53PM -0700, Serguey Zefirov wrote:
> Hello glasgow-haskell-users,
>=20
> The following program
> -----------------------------------------------
> --main =3D print (show (fibs!!200000))
> main =3D print (show (nth 200000 fibs))
>=20
> nth 0 (h:_) =3D h
> nth n (h:t) =3D nth (n-1) t
>=20
> fibs :: [Integer]
> -- fibs =3D 1 : (map snd $ iterate (\(x,y) -> (y, x+y)) (1,1))
> fibs =3D [1..]
> -----------------------------------------------
> compiled with ghc 6.0:
>=20
>   ghc -O -o a.exe a.hs
>=20
> does not execute correctly. It causes stack overflow in 1M stack.
>=20
> If we change "fibs :: [Integer]" to "fibs :: [Int]" the new program
> runs Ok.=20

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

=3D=3D=3D
elementStrict :: [a] -> [a]
elementStrict =3D foldr (($!) (:)) []
=3D=3D=3D

and replacing [1..] by (elementStrict [1..]).

With that, the following program will also work.

=3D=3D=3D
module Main(main) where

main =3D print (fibs!!200000)

fibs :: [Integer]
fibs =3D 1 : elementStrict (map snd $ iterate (\(x,y) -> (y, x+y)) (1,1))
=3D=3D=3D

It produces a result with 41798 decimal digits.

Greetings,

Carsten

--=20
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,=20
fingerprint on my home page.

--O5XBE6gyVG5Rl6Rj
Content-Type: application/pgp-signature
Content-Disposition: inline

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.0.6 (GNU/Linux)
Comment: Weitere Infos: siehe http://www.gnupg.org

iD8DBQE/QhJEWB11G/PFAFgRAlKLAJwOR3mvy3mGOMpF6fH1cuPHcNjP0ACg0obo
jPUbYp+agq4T/Qi/VWFeark=
=QuJH
-----END PGP SIGNATURE-----

--O5XBE6gyVG5Rl6Rj--