user9819885
user9819885

Reputation: 23

Haskell cast Integer to Int

Why the first one is correct and the second one isn't? I'd like to implement the code in the second way so that I won't have to call every time fromInteger, but I don't understand how...

Correct

bits :: Integer -> Int 
bits 0 = 0
bits n = fromInteger n `mod` 2 + bits(fromInteger n `div` 2) 

Incorrect

bits :: Integer -> Int 
bits 0 = 0
bits n = let m = fromInteger n in m `mod` 2 + bits(m `div` 2) 

Upvotes: 2

Views: 2360

Answers (3)

K. A. Buhr
K. A. Buhr

Reputation: 51129

Here is the reason that this version doesn't typecheck:

bits :: Integer -> Int
bits 0 = 0
bits n = let m = fromInteger n in m `mod` 2 + bits(m `div` 2)

First, note that the first usage of m requires that m be an Int because the result of a bits call must be an Int which means the left hand side of the addition (namely m `mod` 2) must be an Int. Why is this? Well, it's because the signature of the + operator is:

(+) :: (Num a) => a -> a -> a

which requires both arguments of + to have the same type as its result. Similarly, because m `mod` 2 must be an Int, the left hand side of the `mod` call (namely m) must be an Int, because mod has signature:

mod :: (Integral a) => a -> a -> a

So, that's why the first usage of m requires m :: Int. Whew!

For much the same reason, the second usage of m requires that m be an Integer. That's because the argument to bits in the expression bits (m `div` 2) must be an Integer which requires that the left hand side of the `div` operator must be an Integer.

Therefore, we have a requirement that m be both an Int and an Integer. This isn't necessarily a problem. If you had instead written:

bits :: Integer -> Int
bits 0 = 0
bits n = m `mod` 2 + bits(m `div` 2)
  where m :: (Integral a) => a
        m = fromInteger n

and given m an explicit polymorphic type signature, then m could be used as both an Int and and Integer simultaneously. However, because of something called the monomorphism restriction, without an explicit type signature, m is required to have a single non-polymorphic (i.e., monomorphic type). If you add the pragma:

{-# LANGUAGE NoMonomorphismRestriction #-}

to the top of your file, then the original definition typechecks fine:

{-# LANGUAGE NoMonomorphismRestriction #-}

bits :: Integer -> Int
bits 0 = 0
bits n = let m = fromInteger n in m `mod` 2 + bits(m `div` 2)

Others have noted, though, that you don't actually need fromInteger in both places; and that using Int and Integer simultaneously is unnecessary, and using a single integer type with a constraint (Integral a) might be even better.

Also, if you wanted this function for real work instead of just practice, it's already available as popCount in module Data.Bits.

Upvotes: 1

Redu
Redu

Reputation: 26191

You may perhaps tweak the signature a little bit and get rid of all fromIntegers.

bits :: Integral a => a -> a 
bits 0 = 0
bits n = n `mod` 2 + bits (n `div` 2)

Upvotes: 1

Bartek Banachewicz
Bartek Banachewicz

Reputation: 39390

Because you don't need it for the 2nd call:

bits :: Integer -> Int 
bits 0 = 0
bits n = fromInteger n `mod` 2 + bits (n `div` 2) 

The 2nd fromInteger simply resulted in Integer again, as forced by the parameter to bits.

Upvotes: 2

Related Questions