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