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