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.

Topic

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

Dyun

Last declaration works for all numbers greater than or equal to 2. For 1 it incorrectly says it is prime, as 1 is not a prime. – Etti

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

Writing

As for idiomatic solutions, I'd suggest truncate . sqrt . fromIntegral for no. 1 and all (\y -> x `mod` y /= 0) [...]. – Rhigolene

Answer 3

Regarding the second point, it stops, for example:

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

Returns False

Kakemono

[x | x <- [1..]] is the same as [1..] btw. – Writing

Answer 4

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.

Oreopithecus

for isPrime to work shortCircuit has to be removed. it matches 25, for example, which is not prime. to compile it I needed brackets around (not $ any divisible $ takeWhile inRangeOf primes), too. – Resentful

that code for primes is quadratic in number of primes produced. The theoretical time complexity of sieve of Eratosthenes is O(n*log n*log (log n)), in n primes produced. The theoretical complexity of trial division is O(n^1.5/(log n)^0.5). Why then that code, which seems to be simple enough trial division, performs that much worse? That's because the firing up of each filter must be postponed until the prime's square is seen in input stream. Diluting the input stream to a third just reduces the constant factor, nothing more. – Aurify

Answer 5

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!

Oreopithecus

1) "import[ing] a module" for Integer is not the issue; the issue is that by his definition, "Instances of (Floating Integer, RealFrac Integer) required for definition of isPrime", just like WinHugs said. 2) Yes, and...? That's so irrelevant, I'm not sure how to respond to that; first, fix the definition so it works, then worry about how to use it. PS) OP's isPrime implementation is not the best, gut it is the one "he" implemented! Help explain how to fix his, write out your own, "or GTFO!" – Mum

1) you are right, I haven't used Haskell for very long time. 2) I was trying to let him know about the Laziness of haskell maybe too trivial PS) he sounds like a student, there is not good reason to give him the answer he should figure it out himself. I have the most optimal isPrime implementation from my university work but I don't see any good coming from it by just posting the answer so he could just copy it and think he is damn good at Haskell. 3) Sort your life out, have some dignity. – Oreopithecus