Strange type-related error

Question

I wrote following program:

isPrime x = and [x `mod` i /= 0 | i <- [2 .. truncate (sqrt x)]]

primes = filter isPrime [1 .. ]

it should construct list of prime numbers. But I got this error:

[1 of 1] Compiling Main             ( 7/main.hs, interpreted )

7/main.hs:3:16:
    Ambiguous type variable `a' in the constraints:
      `Floating a' arising from a use of `isPrime' at 7/main.hs:3:16-22
      `RealFrac a' arising from a use of `isPrime' at 7/main.hs:3:16-22
      `Integral a' arising from a use of `isPrime' at 7/main.hs:3:16-22
    Possible cause: the monomorphism restriction applied to the following:
      primes :: [a] (bound at 7/main.hs:3:0)
    Probable fix: give these definition(s) an explicit type signature
                  or use -XNoMonomorphismRestriction
Failed, modules loaded: none.

If I specify signature for isPrime function explicitly:

isPrime :: Integer -> Bool
isPrime x = and [x `mod` i /= 0 | i <- [2 .. truncate (sqrt x)]]

I can't even compile isPrime function:

[1 of 1] Compiling Main             ( 7/main.hs, interpreted )

7/main.hs:2:45:
    No instance for (RealFrac Integer)
      arising from a use of `truncate' at 7/main.hs:2:45-61
    Possible fix: add an instance declaration for (RealFrac Integer)
    In the expression: truncate (sqrt x)
    In the expression: [2 .. truncate (sqrt x)]
    In a stmt of a list comprehension: i <- [2 .. truncate (sqrt x)]

7/main.hs:2:55:
    No instance for (Floating Integer)
      arising from a use of `sqrt' at 7/main.hs:2:55-60
    Possible fix: add an instance declaration for (Floating Integer)
    In the first argument of `truncate', namely `(sqrt x)'
    In the expression: truncate (sqrt x)
    In the expression: [2 .. truncate (sqrt x)]
Failed, modules loaded: none.

Can you help me understand, why am I getting these errors?

Answer 1

isPrime x = and [x mod i /= 0 | i <- [2 .. truncate (sqrt (fromIntegral x))]]

You're missing a conversion from Integral types to Floating types in the argument for sqrt.

Answer 2

Your problem lies in the call sqrt x. To see why, let's check the type of isPrime in GHCi:

Prelude> let isPrime x = and [x `mod` i /= 0 | i <- [2 .. truncate (sqrt x)]]
Prelude> :t isPrime
isPrime :: (Integral a, Floating a, RealFrac a) => a -> Bool

This tells us that the input to isPrime may be of any type which as an instance of all three specified type classes. In other words, a number which is simultaneously an integer and a real floating point number. While in principle one could declare such a type, it doesn't make much sense; and in fact, no such type does exist.

Now this explains both of your errors. The first error is saying that isPrime is too polymorphic without a type signature. The monomorphism restriction says (roughly) that if you defined a value via a pattern match (such as f = or Just x =, but not g y =), it must not be polymorphic in typeclasses. Thus, since you don't specify a type signature for primes, it infers the type primes :: (Integral a, RealFrac a, Floating a) => [a], and then complains since it's typeclass polymorphic.

The second error comes from the set of the three typeclass constraints you have imposed. mod says that x must be of a type which is an instance of Integral; sqrt says that its input must be of a type which is an instance of Floating; and truncate says that the result of sqrt (which has the same type as its input) must have a type which is an instance of RealFrac. Since these are all used to fulfill identical type variables, x must have all these types at once, and Integer is neither an instance of Floating nor of RealFrac. Consequently, when you specify that isPrime :: Integer -> Bool, you get an error, because Integer needs to be an instance of Floating, but isn't. To solve this problem, we can do a Hoogle search for a conversion function of type (Integral a, Floating b) => a -> b. Sure enough, Hoogle comes up with the more general fromIntegral :: (Integral a, Num b) => a -> b; inserting that before the x in the argument to sqrt will solve your problems, since you will only ever treat x as an instance of Integral. That gives you:

-- The one other change I made: only positive numbers are prime, and 1 is not a
-- prime.
isPrime :: Integral i => i -> Bool
isPrime x | x <= 1    = False
          | otherwise = and [ x `mod` i /= 0
                              | i <- [2..truncate . sqrt $ fromIntegral x] ]

primes :: [Integer]
primes = filter isPrime [2..]

Note that, thanks to the monomorphism restriction, you will still need to give primes a type signature! But it's probably a good idea to anyway.