How is a recursive prime number checker written in Haskell?

Question

I'm very new to Haskell (and functional programming in general), and I'm trying some basic exercises to try to get an understanding of the language. I'm writing a "naive" prime number checker that divides each number under the input to check if there is any remainder. The only constructs I've learned so far are comprehension lists and recursive functions, so I'm constrained to that. Here's what I'm trying:

isprime 1 = False
isprime 2 = True
isprime n = isprimerec n (n-1)

isprimerec _ 1 = False
isprimerec n t = if (n `rem` t) == 0 then False else isprimerec n (n-1)

The intention is that the user would use isprime n. Then isprime would use isprimerec to determine if the number is prime. It's a pretty round-about way of doing it, but I don't know any other way with my limited knowledge of Haskell.

Here's what happens when I try this:

isprimerec 10 9

Runs forever. I have to use Ctrl+C to stop it.

isprimerec 10 5

Returns False. The else part is never evaluated, so the function never calls itself.

I'm not sure why this is happening. Also, is this anywhere near close to how a Haskell programmer would approach this problem? (And I don't mean checking primality, I know this isn't the way to do it. I'm just doing it this way as an exercise).

Answer 1

So OK, you've got the two bugs: your

isprimerec _ 1 = False
isprimerec n t = if (n `rem` t) == 0 then False else isprimerec n (n-1)

should have been

isprimerec _ 1 = True
isprimerec n t = if (n `rem` t) == 0 then False else isprimerec n (t-1)

or, with list comprehension,

isprime n = n>1 && and [ rem n t /= 0 | t <- [n-1,n-2..2] ]

(Internalize that extra parameter t, it was a technicality anyway! -- A-ha, but what's that and, you ask? It's just like this recursive function, foldr (&&) True :: [Bool] -> Bool.)

But now a major algorithmic drawback becomes visually apparent: we test in the wrong order. It will be faster if we test in ascending order:

isprime n = n>1 && and [ rem n t /= 0 | t <- [2..n-1] ]

or even much faster yet if we stop at the sqrt,

isprime n = n>1 && and [ rem n t /= 0 | t <- [2..q] ]
   where  q = floor (sqrt (fromIntegral n))

or test only by odds, after the 2 (why test by 6, if we've tested by 2 already?):

isprime n = n>1 && and [ rem n t /= 0 | t <- 2:[3,5..q] ]
   where  q = floor (sqrt (fromIntegral n))

or just by primes (why test by 9, if we've tested by 3 already?):

isprime n = n>1 && and [ rem n t /= 0 | t <- takeWhile ((<= n).(^2)) primes ]
primes = 2 : filter isprime [3..]  

And why test the evens when filtering the primes through - isn't it better to not generate them in the first place?

primes = 2 : filter isprime [3,5..]  

But isprime always tests division by 2 -- yet we feed it only the odd numbers; so,

primes = 2 : 3 : filter (noDivs (drop 1 primes)) [5,7..]
noDivs factors n = and [ rem n t /= 0 | t <- takeWhile ((<= n).(^2)) factors ]

And why generate the multiples of 3 (i.e. [9,15 ..] == map (3*) [3,5..]), only to test and remove them later? --

{-       [5,7..]
    ==   [j+i | i<-[0,2..], j<-[5]]                 -- loop unrolling, 3x:
    ==   [j+i | i<-[0,6..], j<-[5,7,9]]
    == 5:[j+i | i<-[0,6..], j<-[7,9,11]]            
    == 5:[7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39,41,43, ...
    \\   [  9,      15,      21,      27,      33,      39,       ...
    ==   [j+i | i<-[0,6..], j<-[  9   ]]
-}
primes = 2:3:5: filter (noDivs (drop 2 primes)) 
         [j+i | i<-[0,6..], j<-[7,  11]]

We can skip over the multiples of 5 in advance as well _{(as another step in the Euler's sieve, euler (x:xs) = x : euler (xs `minus` map (x*) (x:xs))):}

--       [j+i | i<-[0, 6..], j<-[7, 11]]            -- loop unrolling, 5x:
--  == 7:[j+i | i<-[0,30..], j<-[11,13,17,19,23,25,29,31,35,37]]
--  \\   [j+i | i<-[0,30..], j<-[               25,      35   ]]

primes = 2:3:5:7: filter (noDivs (drop 3 primes)) 
         [j+i | i<-[0,30..], j<-[11,13,17,19,23,   29,31,   37]]

... but that's already going far enough, for now.

Answer 2

Your bug is a simple typo; at the end of isprimerec, your second parameter becomes n-1 instead of t-1. But that aside, the function isn't quite idiomatic. Here's the first pass of how I would write it:

isPrime :: (Ord a, Integral a) => a -> Bool
isPrime n | abs n <= 1 = False
isPrime 2 = True
isPrime n = go $ abs n - 1
  where go 1 = False
        go t = (n `rem` t /= 0) && go (t-1)

(I might call go something like checkDivisors, but go is idiomatic for a loop.) Note that this exposes the bug in your code: once go is local to isPrime, you don't need to pass n around, and so it becomes clearer that recursing on it is incorrect. The changes I made were, in rough order of importance:

1. I made isprimerec a local function. Nobody else would need to call it, and we lose the extra parameter.

2. I made the function total. There's no reason to fail on 0, and not really any reason to fail for negative numbers. (Technically speaking, p is prime if and only if -p is prime.)

3. I added a type signature. It's a good habit to get into. Using Integer -> Bool, or even Int -> Bool, would also have been reasonable.

4. I switched to interCaps instead of alllowercase. Just formatting, but it's customary.

Except I'd probably make things terser. Manual recursion is usually unnecessary in Haskell, and if we get rid of that entirely, your bug becomes impossible. Your function checks that all the numbers from 2 to n-1 don't divide n, so we can express that directly:

isPrime :: (Ord a, Integral a) => a -> Bool
isPrime n | abs n <= 1 = False
          | otherwise  = all ((/= 0) . (n `rem`)) [2 .. abs n - 1]

You could write this on one line as

isPrime :: (Ord a, Integral a) => a -> Bool
isPrime n = abs n > 1 && all ((/= 0) . (n `rem`)) [2 .. abs n - 1]

but I wouldn't be surprised to see either of these last two implementations. And as I said, the nice thing about these implementations is that your typo isn't possible to make in these representations: the t is hidden inside the definition of all, and so you can't accidentally give it the wrong value.

Answer 3

The problem is in this line

isprimerec n t = if (n `rem` t) == 0 then False else isprimerec n (n-1)

You use (n - 1) as the second argument where it should be (t - 1). A further point, I think you want the isprimerec _ 1 case = True.

As to your more general question of whether or not this is idiomatic, I think you're on the right track. ghci has a decent command line debugger. I found this by putting your code in a file, loading it, and then issuing the command :break isprimerec. I then called your function and stepped through it with :step.

Answer 4

Your else branch is broken since it calls isprimerec n (n-1) every time. You probably ought to write isprimerec n (t-1) instead to have it count down.

You could also use a higher-order function all to make this a lot simpler.

isprime 1 = False
isprime n = all (\t -> n `rem` t /= 0) [2..(n-1)]