Haskell "any" function - primary check

Question

I am trying to define the is_prime function in Haskell. Can anyone point out a problem using any function?

Also, I know that the code below is naive, but I am learning the language starting with babysteps.

 is_prime 0 = False is_prime 1 = False is_prime 2 = True is_prime n = any [n `mod` k == 0 | k <- [2.. sqrt n]] 

Answer 1

Type any - (a -> Bool) -> [a] -> Bool , so it takes a predicate and a collection. Therefore, you should rewrite your last case, for example,

 is_prime n = not $ any (\k -> n `mod` k /= 0) [2 .. ceiling $ sqrt $ fromIntegral n] 

fromIntegral necessary, since the type sqrt Floating a => a -> a , and your n is an integer. Subsequently, without ceiling second argument to any would be Floating t => [t] . This will break because calling mod , whose type is Integral a => a -> a -> a , on non-integer types is illegal.

If you want to find some other implementations, I can recommend, for example, this discussion .

Answer 2

The accepted answer, in my opinion, is incorrect, since the is_prime function actually returns False if n is simple, and here's why.

• any function data returns True as soon as it encounters such an element in data that function data is True .
• \k -> mod nk /= 0 returns True if applied to a number that does not divide some constant n .
• Thus, any returns True if there is a number in the list that does not divide the number n , we want to check for primality and False if it is.
• therefore, is_prime returns True for any number that is divisible by any number in the list [2 .. ceiling $ sqrt $ fromIntegral n] , for example, 4 , which is clearly not simple.

With that said, the correct solution should look like this:

 is_prime n = not $ any (\k -> n `mod` k == 0) [2 .. ceiling $ sqrt $ fromIntegral n] 

This is because the number n is prime if it is not a multiple of any number between 2 and sqrt n .