1
\$\begingroup\$

I wanted to give Haskell a try, and I started with a simple exercise I found here.

  1. Write isPrime :: Integer -> Bool, which determines whether a given integer is prime.
  2. Define primes :: [Integer], the list of all primes.
  3. Revise isPrime so that it only tests divisibility by prime factors.

My answer to Q1

isPrime :: Integer -> Bool
isPrime v = let maxDiv = floor(sqrt (fromIntegral v))
            in all (\x -> (v `rem` x) /= 0) [2..maxDiv]

This one was easy, except for the explicit numeric types conversions I had a hard time to get right.

My answer to Q2

primes = filter isPrime [0..]

This one was easy, too.

My answer to Q3

It took me several hours to answer this one. I quickly understood that isPrime could leverage the values already computed in the array primes. So, my first attempt was :

isPrime :: Integer -> Bool
isPrime v | v < 2 = False
          | otherwise = all (\x -> (v `rem` x) /= 0) (takeWhile (<v) primes)

isPrime works fine for v=0 and v=1, but hangs forever for v>1. Ok, I get it : the mutual recursion creates an infinite loop, due to takeWhile trying to access a primes element which is not yet computed.

One thing I don't understand though, is why primes !! 0 and primes !! 1 hang forever, too.

I tried many approaches for replacing this (takeWhile (<v) primes) by an expression that would stop before reaching a not-yet-computed value. I came to this solution :

isPrime :: Integer -> Bool
isPrime v | v < 2 = False
          | v == 2 = True
          | otherwise = all (\x -> (v `rem` x) /= 0) (takeWhile' (\t -> t*t<=v) primes)

takeWhile' :: (a -> Bool) -> [a] -> [a]
takeWhile' p (x:xs) = if p x then x : takeWhile' p xs else [x]

This solution works. But I had to define a takeWhile' that works just like takeWhile, but also includes the first non-matching element.

Here are my questions to you :

QA : why do primes !! 0 and primes !! 1 hangs in my first attempt ?

QB : is there a magical takeWhileOnlyForAlreadyComputedElements function ? Or a construct that would prevent the infinite loop of this mutual recursion ?

QC : does takeWhile' already exist in the stdlib ? Or maybe the same effect can be achieved in a simpler way ?

\$\endgroup\$
  • \$\begingroup\$ I realize QA may be a better fit on stackoverflow, but the questions I'm more interrested in are QB and QC, which (I think) belong to codereview. \$\endgroup\$ – barjak Sep 7 '11 at 1:55
  • \$\begingroup\$ QC: haskell.org/hoogle/?hoogle=takeWhile Hoogle is very useful. \$\endgroup\$ – AlucardTheRipper Apr 3 '13 at 18:55
4
\$\begingroup\$

Not an answer to your questions, but a correction for your first, looping attempt for Q3:

Things get much easier if you initially have at least one prime number in your list. You could ensure this by a separate case in isPrime, but why not cheat a little bit, and add it directly?

primes = 2 : filter isPrime [3..]

Then you can use your solution for Q1 without much changes (I took the freedom to kill some parens etc):

isPrime :: Integer -> Bool
isPrime v = let maxDiv = floor $ sqrt $ fromIntegral v
            in all ((/= 0).(v `rem`)) $ takeWhile (<= maxDiv) primes

However, this is not the best way to generate a list of primes. Read the excellent paper http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf for details.

[Edit]

I forgot to mention http://www.haskell.org/haskellwiki/Prime_numbers with many interesting techniques.

\$\endgroup\$
  • \$\begingroup\$ Thanks, initializing primes with the first value is clearly the way to go. I'll remember the $ function, too (I saw it in the Prelude, but didn't get its usefulness). \$\endgroup\$ – barjak Sep 7 '11 at 9:00

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.