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

Landei's solution is great, however, if you want a more efficient¹ implementation we have (thanks to BMeph):

-- list of all primes
primes :: [Integer]
primes = sieve (2 : 3 : possible [1..]) where
     sieve (p : xs) = p : sieve [x | x <- xs, x `mod` p > 0]
     possible (x:xs) = 6*x-1 : 6*x+1 : possible xs

isPrime :: Integer -> Bool
isPrime n = shortCircuit || (not $ any divisible $ takeWhile inRangeOf primes) where
    shortCircuit = elem n [2,3] || (n < 25 && ((n-1) `mod` 6 == 0 || (n+1) `mod` 6 == 0))
    divisible y = n `mod` y == 0
    inRangeOf y = y * y <= n

The 'efficiency' comes from the use of constant primes. It improves the search in two ways:

1. The Haskell runtime could cache the results so subsequent invocations are not evaluated
2. It eliminates a range of numbers by logic note that the sieve value is simply a recursive table, where says the head of the list is prime, and adds it to it. For the rest of the lists if there is no other value already in the list that composes the number then its also prime possible is list of all possible primes, since all possible primes are in the form 6*k-1 or 6*k-1 except 2 and 3 The same rule is applied for shortCircuit too to quickly bail out of calculations

Footnote by D.F.
¹ It's still a terribly inefficient way to find primes. Don't use trial division if you need primes larger than a few thousand, use a sieve instead. There are several far more efficient implementations on hackage.

Answer 2

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 3

1. I think WinHugs needs to import a module for Integer and etc... Try Int
2. The interpreter will not compute anything until you call e.g. isPrime 32 then it will lazily compute the expression.

PS your isPrime implementation is not the best implementation!

Answer 4

Regarding the second point, it stops, for example:

[] == [x | x <- [1..]]

Returns False

Answer 5

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 [] ==.