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

You can change (sqrt n) to (sqrt (fromInteger n)) to make the function work as expected. This is needed because the type of sqrt is:

sqrt :: (Floating a) => a -> a

so it is wrong, for example, to do:

sqrt (2 :: Int)

Answer 2

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

Answer 3

Just to go over one last bit that the other answers haven't covered...

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

The typechecker has inferred that prime can take an argument of type a as long as a is an instance of the Integral, RealFrac, and Floating classes all at once.

*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)

When you ask it to prime 5, however, it complains that none of the default types of 5 can satisfy those conditions.

It's quite possible that you could write your own

instance (Integral a, RealFrac b, Floating b) => Integral (Either a b) where ...
instance (Integral a, RealFrac b, Floating b) => RealFrac (Either a b) where ...
instance (Integral a, RealFrac b, Floating b) => Floating (Either a b) where ...

(and you'd also have to add Num, Ord, Real, Fractional, etc. instances), and then prime 5 would be acceptable, since there would exist a 5 :: Either Integer Float which does satisfy the type conditions.

Answer 4

Alternatively, you could change the upper-bound test:

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

Btw, you don't need n as an argument to prime' since it is constant through all calls.