Primality predicate in Haskell

The name of the pictureThe name of the pictureThe name of the pictureClash 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.







share|improve this question



























    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.







    share|improve this question























      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.







      share|improve this 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.









      share|improve this question












      share|improve this question




      share|improve this question








      edited Jan 16 at 14:24









      Jamal♦

      30.1k11114225




      30.1k11114225









      asked Jan 16 at 14:08









      not not totallyhuman

      1134




      1134




















          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.






          share|improve this answer




























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





            share|improve this answer



















            • 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










            Your Answer




            StackExchange.ifUsing("editor", function ()
            return StackExchange.using("mathjaxEditing", function ()
            StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
            StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
            );
            );
            , "mathjax-editing");

            StackExchange.ifUsing("editor", function ()
            StackExchange.using("externalEditor", function ()
            StackExchange.using("snippets", function ()
            StackExchange.snippets.init();
            );
            );
            , "code-snippets");

            StackExchange.ready(function()
            var channelOptions =
            tags: "".split(" "),
            id: "196"
            ;
            initTagRenderer("".split(" "), "".split(" "), channelOptions);

            StackExchange.using("externalEditor", function()
            // Have to fire editor after snippets, if snippets enabled
            if (StackExchange.settings.snippets.snippetsEnabled)
            StackExchange.using("snippets", function()
            createEditor();
            );

            else
            createEditor();

            );

            function createEditor()
            StackExchange.prepareEditor(
            heartbeatType: 'answer',
            convertImagesToLinks: false,
            noModals: false,
            showLowRepImageUploadWarning: true,
            reputationToPostImages: null,
            bindNavPrevention: true,
            postfix: "",
            onDemand: true,
            discardSelector: ".discard-answer"
            ,immediatelyShowMarkdownHelp:true
            );



            );








             

            draft saved


            draft discarded


















            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






























            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.






            share|improve this answer

























              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.






              share|improve this answer























                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.






                share|improve this answer













                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.







                share|improve this answer













                share|improve this answer



                share|improve this answer











                answered Jan 17 at 0:45









                Phil Kiener

                54028




                54028






















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





                    share|improve this answer



















                    • 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














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





                    share|improve this answer



















                    • 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












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





                    share|improve this answer















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






                    share|improve this answer















                    share|improve this answer



                    share|improve this answer








                    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












                    • 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












                     

                    draft saved


                    draft discarded


























                     


                    draft saved


                    draft discarded














                    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













































































                    Popular posts from this blog

                    Chat program with C++ and SFML

                    Function to Return a JSON Like Objects Using VBA Collections and Arrays

                    Will my employers contract hold up in court?