2
\$\begingroup\$

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.

\$\endgroup\$
5
\$\begingroup\$

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.

\$\endgroup\$
-1
\$\begingroup\$

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..]])
\$\endgroup\$
  • 2
    \$\begingroup\$ Can you explain why this is an improvement? I find the original code easier to understand. \$\endgroup\$ – mkrieger1 Jan 17 '18 at 15:44
  • \$\begingroup\$ 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. \$\endgroup\$ – Gurkenglas Jan 17 '18 at 22:04
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – mkrieger1 Jan 17 '18 at 22:12
  • \$\begingroup\$ 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. \$\endgroup\$ – Gurkenglas Jan 18 '18 at 15:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.