Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Unusual Problem with Haskell

Tags:

haskell

I am running ghci from Terminal.

In my source file, I defined

factorial :: Int -> Int
factorial n = product [1 .. n]

When I run this, I get the result

factorial 13 = 1932053504

product [1 .. 13] = 6227020800

For any number less than 13, the result is correct. However, for any number greater than or equal to 12, the two result do not agree.

Also if I define this function recursive :

factorial' :: Int -> Int
factorial' 0 = 1
factorial' (n + 1) = (n + 1) * factorial' n

I still get

factorial' 13 = 1932053504

If you understand what is occurring here, it would be very helpful. Thanks

like image 444
user898033 Avatar asked Nov 27 '22 09:11

user898033


2 Answers

According to the documentation for Int: A fixed-precision integer type with at least the range [-2^29 .. 2^29-1]. Your factorial function is typed to use a an Int, which is overflowing. Now, if we check out the type of the second answer (from simply using product in GHCi), we see that it is of type Integer:

Prelude> let a = product [1 .. 13]
Prelude> :t a
a :: Integer

Integer is unbounded, and so is able to hold such a large number without overflowing.

like image 181
kylc Avatar answered Dec 05 '22 02:12

kylc


You have the wrong types: Int wraps around somewhere (probably 2^31), you need Integer for unlimited integer values:

factorial :: Integer -> Integer
factorial n = product [1 .. n]
like image 37
Landei Avatar answered Dec 05 '22 02:12

Landei