Haskell prime test

Question

I'm new to Haskell, and I'm trying a bit:

isPrime :: Integer->Bool
isPrime x = ([] == [y | y<-[2..floor (sqrt x)], mod x y == 0])

I have a few questions.

1. Why when I try to load the .hs, WinHugs say: Instances of (Floating Integer, RealFrac Integer) required for definition of isPrime?
2. When the interpreter finds one element in the right set, it immediately stops or it computes all the set? I think you know what I mean.

Sorry about my english.

Answer 1

1) The problem is that sqrt has the type (Floating a) => a -> a, but you try to use an Integer as argument. So you have to convert your Integer first to a Floating, e.g. by writing sqrt (fromIntegral x)

2) I see no reason why == shouldn't be lazy, but for testing for an empty collection you can use the null function (which is definitely lazy, as it works on infinite lists):

isPrime :: Integer->Bool
isPrime x = null [y | y<-[2..floor (sqrt (fromIntegral x))], x `mod` y == 0]

But in order to get an more idiomatic solution, break the problem into smaller sub-problems. First, we need a list of all elements y with y*y <= x:

takeWhile (\y ->  y*y <= x) [2..]

Then we need only the elements that divide x:

filter (\y ->  x `mod`y == 0) (takeWhile (\y ->  y*y <= x) [2..])

Then we need to check if that list is empty:

isPrime x = null (filter (\y ->  x `mod`y == 0) (takeWhile (\y ->  y*y <= x) [2..]))

And if this looks to lispy to you, replace some of the parens with $

isPrime x = null $ filter (\y ->  x `mod` y == 0) $ takeWhile (\y ->  y*y <= x) [2..]

For additional clarity you can "outsource" the lambdas:

isPrime x = null $ filter divisible $ takeWhile notTooBig [2..] where
     divisible y = x `mod`y == 0
     notTooBig y = y*y <= x

You can make it almost "human readable" by replacing null $ filter with not $ any:

isPrime x = not $ any divisible $ takeWhile notTooBig [2..] where
     divisible y = x `mod`y == 0
     notTooBig y = y*y <= x

Answer 2

1. Because sqrt has the type Floating a => a -> a. This means the input has to be a Floating type and the output will be the same type. In other words x needs to be a Floating type. However you declared x to be of type Integer, which is not a Floating type. In addition floor needs a RealFrac type, so x needs to be that as well.

   The error message suggests that you fix that by making Integer a Floating type (by defining an instance Floating Integer (and the same for RealFrac).

   Of course this is not the correct approach in this case. Rather you should use fromIntegral to convert x to a Real (which is an instance of Floating and RealFrac) and then give that to sqrt.

2. Yes. As soon as == sees that the right operand has at least one element, it knows it is not equal to [] and thus returns False.

   That being said, null is a more idiomatic way to check whether a list is empty than [] ==.