CODEWITHSUNDEEP
haskell
unexim
unexim

Reputation: 55

Prime number program in haskell

I was looking up a program in Haskell that tests if a given number is prime or not. 

prime :: (Integral a) => a -> Bool
prime 1 = True
prime x = and [ x `mod` y /= 0 | y <- [2..(x-1)] ]

I don't understand what is the purpose of this and in: prime x = and [.

Upvotes: 2

Views: 532

Answers (3)

ScarletAmaranth
ScarletAmaranth

Reputation: 5101

and performs a logical and operation on all elements of a list.

Primes are only divisible by one and themselves; this means that as soon as a divisor (without a remainder) exists between 2 inclusive and your x exclusive, the number is not a prime.

The list comprehension generates a list of Boolean values that correspond to whether your x is or is not divisible by numbers from within the said range.

As soon as any of them is false (a division occurred with a zero remainder), the number is not a prime.

Consider:

x = 7
[7 % 2 /= 0 -> True, 7 % 3 /= -> True, ...]
-- now applying and
True && True && ... && True evaluates to True

and can be represented as a more general operation that can be performed on lists - a fold using logical and. Such as: and' = foldr (&&) True.

Upvotes: 2

eazar001
eazar001

Reputation: 1601

Although this question has been answered, please allow me to add a few things: When examining the source of and, you get:

and :: [Bool] -> Bool
and = foldr (&&) True

First thing to notice is that and takes a list of Boolean variables, and returns a single Boolean variable, and that the expression x mod y /= 0 evaluates to True or False (Hence fitting the [Bool] requirement) .

More important to notice is that foldr is a lazy-fold. So a lazy fold here is optimal because && is a semi-strict operator. Hence a lazy fold in combination with a semi-strict operator will yield a short-circuit evaluation upon encountering the first occurence of a False. Hence in the cases of actual non-prime numbers, and will avoid evaluating the entire list, consequently saving you time as a result. Don't take my word for it, define your own strict version of and if you want (using the stricter foldl):

andStrict :: [Bool] -> Bool
andStrict x = foldl (&&) True

primeStrict :: (Integral a) => a -> Bool
primeStrict x = andStrict [x `mod` y /= 0 | y <- [2..(x-1)]]

Now run:

prime 2000000000

Notice how that was fast? Now do this, but interrupt it before it crashes your memory-stack:

primeStrict 2000000000

That was obviously slower, you were able to interrupt it. This is the role of and, and that is why and was written with foldr, and hence why it was chosen for the example code you posted. Hope that helps as a supportive answer.

Upvotes: 2

bheklilr
bheklilr

Reputation: 54078

The expression

[x `mod` y /= 0 | y <- [2..(x - 1)]

is a list of Bools because mod x y /= 0 (prefix notation because of backtick formatting) returns a Bool. The and function just does a logical AND of every element in a list, so

and [True, False] == False
and [True, True] == True

Upvotes: 2

Related Questions