I have a working (albeit inefficient) function to check if a number is prime in Python and I'd like to convert it to Haskell. Efficiency doesn't matter to me right now as I am focusing primarily on making a readable algorithm in Haskell that uses language features a beginner would understand.
I'm new to Haskell so I may have the wrong mindset about how to approach this. My basic algorithm is to check if a number is odd and above 2 and if so, check if it's divisible by any number before until 2.
Problem: I don't know how to set i equal to an increasing term in the range [2..n].
Question: Is there a way to iterate over a range with a variable and refer to it?
Python:
def is_prime(n):
if n < 2:
return False # by definition, numbers smaller than 2 are not prime
if n == 2: # edge case, 2 is the only even number that is prime
return True
if (n % 2) == 0:
return False # if even, n is not prime (except 2)
else:
for i in range(2,n): #iterate from 2 to the input(n)-1 (since range() is non-inclusive of stop param)
if (n % i == 0): #if n is divisible by a number that isn't 1 or itself...
return False # ...it isn't prime
return True
Haskell (What I have so far):
isPrimeInner :: Int -> Bool
isPrimeInner n = map (n `rem` i == 0) [2..n] where i
-- I don't know how to set i equal to an increasing term
-- in the range [2..n]
isPrime :: Int -> Bool
isPrime 2 = True -- edge case
isPrime n = if n < 2
then False
else if n `rem` 2 == 0
then False
else isPrimeInner n
Simplest done with List Comprehensions:
isPrime :: Int -> Bool
isPrime n = n > 1 && ( n == 2 ||
null [ () | i <- [2..n-1], rem n i == 0] )
-- ~~~~~~~~~~~~~
Here i is drawn from the range 2 .. n-1, i.e. it takes on the increasing values from 2 to n-1, one at a time.
When it divides n evenly without a remainder, a () value is produced as a member of the output list, which is then tested for being empty, with null. The code thus expresses the concept "there does not exist such i from 2 to n-1 that divides n evenly".
The i <- [2..n-1] part is known as a generator part of a list comprehension, and rem n i == 0 a test expression.
Testing:
> filter isPrime [0..545]
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,
137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,
271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,
431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541]
it :: [Int]
> length it
100
Thanks to Haskell's lazy evaluation, when given a composite argument n, isPrime fails as soon as possible, with the smallest divisor i of n.