What is the type signature of this Haskell function?

Question

I wrote a function to check whether a number is prime or not:

prime n = prime' n 2 (floor (sqrt n))
     where prime' n c u | n `mod` c == 0 = False
                        | c > u = True
                        | otherwise = prime' n (c+1) u

I can't figure out what the type signature of this function should be. At first I thought it should be this:

prime :: Integral a => a -> Bool

But then I get errors when compiling because sqrt expects a Floating a and floor expects a RealFrac a instead of an Integral a. When I remove the type signature, it compiles, but the function does not work:

*Euler> :t prime
prime :: (Integral a, RealFrac a, Floating a) => a -> Bool
*Euler> prime 5

<interactive>:1:0:
    Ambiguous type variable `t' in the constraints:
      `Floating t' arising from a use of `prime' at <interactive>:1:0-6
      `RealFrac t' arising from a use of `prime' at <interactive>:1:0-6
      `Integral t' arising from a use of `prime' at <interactive>:1:0-6
    Probable fix: add a type signature that fixes these type variable(s)

How can I make this function work?

Answer 1

The problem is that you use sqrt on n, which forces n to be a floating-point number; and you also use mod on n, which forces n to be an integer. Intuitively, from looking at your code, n should be an integer, so you can't directly call sqrt on it. Instead, you can use something like fromIntegral to convert it from an integer into another numeric type.

prime :: (Integral a) => a -> Bool
prime n = prime' n 2 (floor (sqrt (fromIntegral n)))
     where prime' n c u | n `mod` c == 0 = False
                        | c > u = True
                        | otherwise = prime' n (c+1) u