Reputation: 23
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
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
Reputation: 26191
You may perhaps tweak the signature a little bit and get rid of all fromInteger
s.
bits :: Integral a => a -> a
bits 0 = 0
bits n = n `mod` 2 + bits (n `div` 2)
Upvotes: 1
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