CODEWITHSUNDEEP
haskelltypesinteger
ntdef
ntdef

Reputation: 504

Dubious 'Int' vs 'Integer' handling in Haskell?

Just for kicks, I wanted to see what would happen if I defined a function in Haskell as Int -> Int, knowing that it would overflow and have to return an Integer. Consider the following:

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

Now I know that if I run factorial 50, I'm going to get a number outside of the 'codomain' of factorial. Since Haskell is so strongly typed, I was hoping it would return an error. Instead GHCi returns a weird negative Int:

ghci> factorial 50
-3258495067890909184

And note that 

ghci> maxBound :: Int
9223372036854775808

since I'm running on 64 bit.

I find this behavior kind of scary: why doesn't Haskell raise an error? And why does factorial 50 return a random negative number? Any clarification would be greatly appreciated.

Upvotes: 5

Views: 3519

Answers (1)

amindfv
amindfv

Reputation: 8448

The Int type is defined as "A fixed-precision integer type with at least the range [-2^29 .. 2^29-1]." [0] The range varies by machine but you can find it with minBound and maxBound

The reason it overflows is that it's got a fixed amount of memory allocated for it. Imagine a simpler example - a positive integer in memory whose maximum value was 7 (stored as 3 bits in memory)

0 is represented as 000, in binary
1 is represented as 001
2 is represented as 010, etc.

Note how the bit math works: when you add 1, you either turn the smallest digit from 0 to 1, or you turn it from 1 to 0 and do the same operation on the next-most-significant digit.

So for example, 011 + 1 is 100.

Now if you naievely (as Haskell does) perform this when there's no next-most-significant digit, then it just increments as usual, but "gets its head cut off." E.g. 111 + 1 becomes 000 instead of 1000. This is what's happening with Haskell, except that its lowest value (represented as a series of 0s) is its lowest negative number. it uses its "leftmost" bit to represent +/-. You'll need to do (maxBound :: Int) + (maxBound :: Int) + 2 to get 0.

So similarly:

>  maxBound :: Int  
9223372036854775807  
>  (maxBound :: Int) + 1  
-9223372036854775808  
>  (maxBound :: Int) + 2  
-9223372036854775807  
>  let x = (maxBound :: Int) + 1 in x + x
0

Why "allow" this to happen? Simple - efficiency. It's much faster to not check for if there'll be an integer overflow. This is the reason that Integer exists - it's unbounded, for when you think you might overflow, but you pay a price in efficiency.

[0] http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data-Int.html

Upvotes: 20

Related Questions