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)
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.
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.
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)
bits n = fromInteger (n`mod`2) + bits (n`div`2). Alternativelycase n`divMod`2 of (q,r) -> fromInteger r + bits q.bitsbetter than simply callingfromInteger? Aside from using more CPU cycles,bitsisfromInteger. You're basically converting12 :: Integerto12 :: Intby recognizing that12 == 8 + 4, then adding8and4to get back12.