Primality predicate in Haskell

Question

I wrote a primality test for UniHaskell however, it seems complicated in terms of conditionals.

Here it is, rewritten to not use Unicode and other functions in the code:

-- Primality predicate
isPrime :: Int -> Bool
isPrime 2 = True
isPrime 3 = True
isPrime n
 | n `mod` 2 == 0 = False
 | n `mod` 3 == 0 = False
 | otherwise = check 5 2
 where check i w
 | i * i <= n = if n `mod` i == 0
 then False
 else check (i + w) (6 - w)
 | otherwise = True

The algorithm is simple: return True if n is 2 or 3, False if n is a multiple of 2 or 3, and then perform trial division over numbers that are not multiples of 2 or 3.

Answer 1

All in all, that is some good looking, idiomatic Haskell. Well done!

---

You seem to be using the mod n x == 0 idiom quite often, so let's extract that to its own function.

divides :: Integral a => a -> a -> Bool
n `divides` m = m `mod` n == 0

---

You could also make your predicate polymorphic. No need to restrict yourself to Int, any Integral will do the trick.

isPrime :: Integral a => a -> Bool
isPrime 2 = True
-- and so on

---

I've often read that rem is faster than mod, but I've never checked... maybe it does give you some speed.

---

Through clever reordering of the guards, you can get rid of the if then else.

---

Instead of having a simple comment to explain the function, consider writing actual Haddock documentation.

---

Putting it together:

-- | @divides n m@ checks whether @n@ evenly
-- divides @m@, meaning that @m `mod` n == 0@.
divides :: Integral a => a -> a -> Bool
n `divides` m = m `rem` n == 0
-- | Checks whether a given number is prime.
isPrime :: Integral a => a -> Bool 
isPrime 2 = True
isPrime 3 = True
isPrime n 
 | 2 `divides` n = False
 | 3 `divides` n = False 
 | otherwise = check 5 2 
 where check i w 
 | i * i > n = True
 | i `divides` n = False
 | otherwise = check (i + w) (6 - w)

Maybe check 5 2 deserves a comment, as I couldn't see why these numbers are there on a first glance.

Answer 2

Replace recursion by control structures.

isPrime n = elem n [2,3] || all ((/=0) . mod n)
 (takeWhile (\i -> i * i <= n) $ 2 : 3 : concat [[i, i+2] | i <- [5,11..]])

• mkrieger1: Can you explain why this is an improvement? I find the original code easier to understand.
• Gurkenglas: Looking at the original code without its name or comments, it took me a while to understand why it shuffled around the numbers the way it did in check, so I made the code say explicitly that it runs a check on a bunch of numbers.
• mkrieger1: That sounds reasonable. Why don’t you include that in your answer? I think more could be learned from it if it explained more, instead of merely showing.
• Gurkenglas: That's what "Replace recursion by control structures." is for. A good heuristic for whether code shuffles its numbers around in a confusing way is whether it is recursive. Structures such as lists can classify the form of recursion used. I shall start including explanatory links.