I don't understand number conversions in Haskell

Question

Here is what I'm trying to do:

isPrime :: Int -> Bool
isPrime x = all (\y -> x `mod` y /= 0) [3, 5..floor(sqrt x)]

(I know I'm not checking for division by two--please ignore that.) Here's what I get:

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 x)'
In the expression: floor (sqrt x)
In the second argument of `all', namely `[3, 5 .. floor (sqrt x)]'

I've spent literally hours trying everything I can think of to make this list using some variant of sqrt, including nonsense like

intSqrt :: Int -> Int
intSqrt x = floor (sqrt (x + 0.0))

It seems that (sqrt 500) works fine but (sqrt x) insists on x being a Floating (why?), and there is no function I can find to convert an Int to a real (why?).

I don't want a method to test primality, I want to understand how to fix this. Why is this so hard?

Answer 1

Unlike most other languages, Haskell distinguishes strictly between integral and floating-point types, and will not convert one to the other implicitly. See here for how to do the conversion explicitly. There's even a sqrt example :-)

The underlying reason for this is that the combination of implicit conversions and Haskel's (rather complex but very cool) class system would make type reconstruction very difficult -- probably it would stretch it beyond the point where it can be done by machines at all. The language designers felt that getting type classes for arithmetic was worth the cost of having to specify conversions explicitly.

Answer 2

Your issue is that, although you've tried to fix it in a variety of ways, you haven't tried to do something x, which is exactly where your problem lies. Let's look at the type of sqrt:

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

On the other hand, x is an Int, and if we ask GHCi for information about Floating, it tells us:

Prelude> :info Floating
class (Fractional a) => Floating a where
  pi :: a
  <...snip...>
  acosh :: a -> a
    -- Defined in GHC.Float
instance Floating Float -- Defined in GHC.Float
instance Floating Double -- Defined in GHC.Float

So the only types which are Floating are Floats and Doubles. We need a way to convert an Int to a Double, much as floor :: (RealFrac a, Integral b) => a -> b goes the other direction. Whenever you have a type question like this, you can ask Hoogle, a Haskell search engine which searches types. Unfortunately, if you search for Int -> Double, you get lousy results. But what if we relax what we're looking for? If we search for Integer -> Double, we find that there's a function fromInteger :: Num a => Integer -> a, which is almost exactly what you want. And if we relax our type all the way to (Integral a, Num b) => a -> b, you find that there is a function fromIntegral :: (Integral a, Num b) => a -> b.

Thus, to compute the square root of an integer, use floor . sqrt $ fromIntegral x, or use

isqrt :: Integral i => i -> i
isqrt = floor . sqrt . fromIntegral

You were thinking about the problem in the right direction for the output of sqrt; it returned a floating-point number, but you wanted an integer. In Haskell, however, there's no notion of subtyping or implicit casts, so you need to alter the input to sqrt as well.

To address some of your other concerns:

intSqrt :: Int -> Int
intSqrt x = floor (sqrt (x + 0.0))

You call this "nonsense", so it's clear you don't expect it to work, but why doesn't it? Well, the problem is that (+) has type Num a => a -> a -> a—you can only add two things of the same type. This is generally good, since it means you can't add a complex number to a 5×5 real matrix; however, since 0.0 must be an instance of Fractional, you won't be able to add it to x :: Int.

It seems that (sqrt 500) works fine…

This works because the type of 500 isn't what you expect. Let's ask our trusty companion GHCi:

Prelude> :t 500
500 :: (Num t) => t

In fact, all integer literals have this type; they can be any sort of number, which works because the Num class contains the function fromInteger :: Integer -> a. So when you wrote sqrt 500, GHC realized that 500 needed to satisfy 500 :: (Num t, Floating t) => t (and it will implicitly pick Double for numeric types like that thank to the defaulting rules). Similarly, the 0.0 above has type Fractional t => t, thanks to Fractional's fromRational :: Rational -> a function.

… but (sqrt x) insists on x being a Floating …

See above, where we look at the type of sqrt.

… and there is no function I can find to convert an Int to a real ….

Well, you have one now: fromIntegral. I don't know why you couldn't find it; apparently Hoogle gives much worse results than I was expecting, thanks to the generic type of the function.

Why is this so hard?

I hope it isn't anymore, now that you have fromIntegral.