Prime number function with Haskel

Question

Given a natural number $n> 0$, define a function IsPrime(n) that tells whether it is, or not, a prime number.

I tried do two functions:

HasDivider(x,y) | FALSE if y = 1
                | TRUE if mod(x,y) = 0
                | HasDivider(x, y-1) if mod(x,y) > 0

IsPrime(n) | TRUE if HasDivider(n, n/2) = FALSE
           | FALSE if HasDivider(n, n/2) = TRUE

There is any error? or other way to do?

Answer 1

There are many of issues with the code sample you have provided, beyond the fact that it is mathematically unsound. I would encourage you to post this on StackOverflow for feedback concerning your use of Haskell.

Consider the value of IsPrime at $n=2$. Is it not true that $2 \equiv 0 \pmod{1}$? Or in Haskell,

2 `mod` 1 == 0

Hence, as written, your function will find 2 to be a composite number.

---

In case it proves helpful, the following summarizes a few of the issues with you Haskell sample.

1. The syntax for function declarations is HasDivider x y, not HasDivider(x,y)
2. Likewise, for function calls its HasDivider a b not HasDivider(a,b)
3. The Bool constants are True and False, not TRUE and FALSE
4. The operator / performs floating point division. You want integer division, which uses div.
5. While not explicitly incorrect, you should be mindful of the difference between rem and mod. For you purposes, rem should be preferred, as it is generally faster.
6. Your pattern matching uses completely invalid syntax.
7. Your pattern matching is non-exhaustive.
8. if does not exist in the way you are trying to use it.
9. You are making the compiler infer all types.

Your (still inefficient) function might resemble the following in valid Haskell

hasDivider :: Integral a => a -> a -> Bool
hasDivider _  1 = False
hasDivider x y = x `mod` y == 0 ||  hasDivider x (y-1)

isPrime :: Integral a => a -> Bool
isPrime n = not $ hasDivider n (n `div` 2)

main :: IO ()
main = print $ isPrime 2