Primality predicate in Haskell

Clash Royale CLAN TAG#URR8PPP
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty margin-bottom:0;
up vote
2
down vote
favorite
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.
haskell primes
add a comment |Â
up vote
2
down vote
favorite
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.
haskell primes
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
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.
haskell primes
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.
haskell primes
edited Jan 16 at 14:24
Jamalâ¦
30.1k11114225
30.1k11114225
asked Jan 16 at 14:08
not not totallyhuman
1134
1134
add a comment |Â
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
4
down vote
accepted
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.
add a comment |Â
up vote
-1
down vote
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..]])
2
Can you explain why this is an improvement? I find the original code easier to understand.
â mkrieger1
Jan 17 at 15:44
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.
â Gurkenglas
Jan 17 at 22:04
1
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.
â mkrieger1
Jan 17 at 22:12
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.
â Gurkenglas
Jan 18 at 15:59
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
4
down vote
accepted
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.
add a comment |Â
up vote
4
down vote
accepted
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.
add a comment |Â
up vote
4
down vote
accepted
up vote
4
down vote
accepted
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.
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.
answered Jan 17 at 0:45
Phil Kiener
54028
54028
add a comment |Â
add a comment |Â
up vote
-1
down vote
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..]])
2
Can you explain why this is an improvement? I find the original code easier to understand.
â mkrieger1
Jan 17 at 15:44
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.
â Gurkenglas
Jan 17 at 22:04
1
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.
â mkrieger1
Jan 17 at 22:12
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.
â Gurkenglas
Jan 18 at 15:59
add a comment |Â
up vote
-1
down vote
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..]])
2
Can you explain why this is an improvement? I find the original code easier to understand.
â mkrieger1
Jan 17 at 15:44
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.
â Gurkenglas
Jan 17 at 22:04
1
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.
â mkrieger1
Jan 17 at 22:12
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.
â Gurkenglas
Jan 18 at 15:59
add a comment |Â
up vote
-1
down vote
up vote
-1
down vote
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..]])
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..]])
edited Jan 19 at 14:06
answered Jan 17 at 13:36
Gurkenglas
2,658411
2,658411
2
Can you explain why this is an improvement? I find the original code easier to understand.
â mkrieger1
Jan 17 at 15:44
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.
â Gurkenglas
Jan 17 at 22:04
1
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.
â mkrieger1
Jan 17 at 22:12
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.
â Gurkenglas
Jan 18 at 15:59
add a comment |Â
2
Can you explain why this is an improvement? I find the original code easier to understand.
â mkrieger1
Jan 17 at 15:44
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.
â Gurkenglas
Jan 17 at 22:04
1
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.
â mkrieger1
Jan 17 at 22:12
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.
â Gurkenglas
Jan 18 at 15:59
2
2
Can you explain why this is an improvement? I find the original code easier to understand.
â mkrieger1
Jan 17 at 15:44
Can you explain why this is an improvement? I find the original code easier to understand.
â mkrieger1
Jan 17 at 15:44
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.
â Gurkenglas
Jan 17 at 22:04
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.
â Gurkenglas
Jan 17 at 22:04
1
1
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.
â mkrieger1
Jan 17 at 22:12
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.
â mkrieger1
Jan 17 at 22:12
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.
â Gurkenglas
Jan 18 at 15:59
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.
â Gurkenglas
Jan 18 at 15:59
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f185221%2fprimality-predicate-in-haskell%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password