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..]])