Haskell “No instance for” error

Question

I am trying to write a function that checks if a number is prime. I wrote this :

primeCheck :: Int -> Int -> Bool
primeCheck n i 
    | n == 2 = True
    | i == 1 = True
    | n `mod` i == 0 = False
    | otherwise = primeCheck n (i -1)

isPrime :: Int -> Bool
isPrime n = primeCheck n (floor (sqrt n))

And I get these errors :

No instance for (RealFrac Int) arising from a use of floor' Possible fix: add an instance declaration for (RealFrac Int) In the second argument ofprimeCheck', namely (floor (sqrt n))' In the expression: primeCheck n (floor (sqrt n)) In an equation forisPrime': isPrime n = primeCheck n (floor (sqrt n))

No instance for (Floating Int)
  arising from a use of `sqrt'
Possible fix: add an instance declaration for (Floating Int)
In the first argument of `floor', namely `(sqrt n)'
In the second argument of `primeCheck', namely `(floor (sqrt n))'
In the expression: primeCheck n (floor (sqrt n)) Failed, modules loaded: none.

When I change the code to this to hopefully fix the problem:

primeCheck :: Int -> Int -> Bool
primeCheck n i 
    | n == 2 = True
    | i == 1 = True
    | n `mod` i == 0 = False
    | otherwise = primeCheck n (i -1)

isPrime :: Int -> Bool
isPrime n = primeCheck n (floor (RealFrac (sqrt  (Floating n))))

I get this :

Not in scope: data constructor `RealFrac'

Not in scope: data constructor `Floating'

How can I fix this?

Answer 1

Floating is a typeclass, not a constructor or function. You do seem to have figured out that you need to convert the type of n. The correct way to do this would be using fromIntegral:

isPrime n = primeCheck n $ floor $ sqrt $ (fromIntegral n :: Double)

We can see why this works by following the type signatures of the functions.

From the type signature of isPrime, we see n has type Int.

Since sqrt expects some Floating type (i.e. a type that is an instance of the typeclass Floating), we can convert from an Int to a Double using fromIntegral. Note that the signature of fromIntegral is

(Integral a, Num b) => a -> b

Int is an instance of Integral (so the input type is okay) and Double is an instance of Num so the output type is okay.

Then we take the sqrt to get a new Double.

floor expects an argument whose type is an instance of RealFrac. Double happens to be an instance of both Floating and RealFrac, so it will do the job (no conversion necessary). floor will convert the square root back to type Int.

Note that since the output type of fromIntegral is polymorphic, as is the input type of sqrt and floor, we have to specify the type of the conversion as Double, otherwise the compiler won't know which Num/Floating/RealFrac instance to convert to. You might see the error ambiguous type 'a' in ....

You can see the type signatures of many functions using Hoogle

EDIT

It turns out the explicit type signature for the fromIntegral is not required. Thus

isPrime n = primeCheck n $ floor $ sqrt $ fromIntegral n

suffices. In my opinion, it would be clearer to just provide the explicit signature, but it is not necessary in this case. You can read more about it here.

Answer 2

The problem is in converting from the Int for use in sqrt. Change the last line to

isPrime n = primeCheck n (floor (sqrt (fromIntegral n)))

Answer 3

Floating and RealFrac are type-classes, not functions.

This page gives a good overview of the standard Haskell numeric type-class hierarchy (section 6.3):

http://www.haskell.org/onlinereport/basic.html

In particular, this diagram of the type-classes is very helpful:

http://www.haskell.org/onlinereport/classes.gif

You clearly want to take the square root of an Int by using the floating point sqrt and floor functions. The problem is that these functions have the following types:

sqrt :: Floating a => a -> a
floor :: (Integral b, RealFrac a) => a -> b

The obstacles are:

1. sqrt takes a Floating argument, and Int is not in the Floating type class
2. floor requires a RealFrac argument, but sqrt produces only a Floating

You can solve the first with the fromIntegral function:

fromIntegral :: (Integral a, Num b) => a -> b

which will allow you to convert an Int (or any other integral type) into any Num type (which includes Floating.)

Next, looking at the chart of the numeric type-class hierarchy we see that Double and Float are members of both the Floating and RealFrac type-classes.

So by an explicit type coercion to Double you can apply floor:

isqrt :: Int -> Int
isqrt n = floor (sqrt (fromIntegral n) :: Double)

Now, as @lthread mentioned, you can get away with:

isqrt :: Int -> Int
isqrt n = (floor . sqrt . fromIntegral) n

and GHC will default the return type of sqrt to Double. It's perfectly fine to do this, but you should be aware that it is happening. For example, if you want to use this approach to take the integer square-root of an Integer, you want to pass through an abritrary precision real type (like a Data.Number.BigFloat) instead of a Double.