I wanted to give Haskell a try, and I started with a simple exercise I found here.
isPrime :: Integer -> Bool, which determines whether a given integer is prime.
primes :: [Integer], the list of all primes.
isPrimeso 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 ?