Converting isPrime() Python to Haskell

Question

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

Answer 1

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.

Answer 2

There is no assignment in Haskell. Unfortunately you hit a topic that requires you to learn a new concept: Instead of focusing on a single value (x) you should focus on the complete range/list of values.

Let's assume n = 8. A Python programmer might iterate (x in i in range(2, n)), a Haskell programmer might convert the input list [2..n] into a result list and continue to solve the problem from there:

xs = [   2,     3,    4,     5, ...]  -- input [2..n]
ys = [True, False, True, False, ...]  -- the resulting list of the divisibility test

Therefore I propose to break the problem down and solve the two sub-problems:

1. How to compute ys from xs?
2. Assuming your have the list of divisibility tests (ys). How can you solve your original problem? In your case having any True value as an element is important. Fortunately there is a function any that can help you.

Answer 3

Instead of using a loop, try to convert it to a tail recursion.

isPrimeHelper :: Integer -> [Integer] -> Bool
isPrimeHelper p (i:is) 
    | i*i > p = True
    | p `rem` i == 0 = False
    | otherwise = isPrimeHelper p is

isPrime :: Integer -> Bool
isPrime p = isPrimeHelper p [2..p]

the isPrimeHelper is the recursion version of the loop and the i appear in it is just like the i in the loop, and you can keep track of it.

for the equivalent Python code:

def isPrimeHelper(p : int, xs : [int]):
  i = xs[0]
  if i*i >p:
    return True
  elif p % i == 0:
    return False
  else:
    return isPrimeHelper(p, xs[1:])