Function that tells if a number ir prime or not-CodePudding

`` I'm a Haskell newbie and I'm defining a function that given an Int n it tells if a number is prime or not by searching for an 2<=m<=sqrt(n) that mod n m ==0 if such m exists, then n is not prime, if not then n is prime. I'm trying to define a list with numbers m between 2 and sqrt n, that mod n m ==0 My thought is that if the list is empty then n is prime, it not, n is not prime `

isprime' :: Int -> Bool           
isprime' n | l == [] = True
           | otherwise = False

           where 
            l = [x|x<-[2.. sqrt n], mod n x == 0]

But there seems to be a problem with sqrt n when I run my code and I can't understand it. can someone explain what I'm doing wrong/what to change for my code to run/ and why there's an error?

CodePudding user response：

Running the code gives the following error

test.hs:9:28: error:
    • No instance for (Floating Int) arising from a use of ‘sqrt’
    • In the expression: sqrt n
      In the expression: [2 .. sqrt n]
      In a stmt of a list comprehension: x <- [2 .. sqrt n]
  |
9 |             l = [x|x<-[2.. sqrt n], mod n x == 0]
  |                            ^^^^^^

You are correct in saying that the error is with sqrt, but the rest is pretty opaque to a new Haskell developer. Lets try by checking the type of sqrt to see if that helps.

Prelude> :t sqrt
sqrt :: Floating a => a -> a

Here I'm using ghci to interactively write code. :t asks for the type of the preceeding expression. The line sqrt :: Floating a => a -> a says sqrt takes in some floating point number a and returns something of the same type.

Similar to our error message we see this Floating thing. this thing is a typeclass but for the sake of solving this problem we'll save understanding those for later. In essence, haskell is trying to tell you that Int is not floating point number which is what sqrt expects. We can amend that by turning our Int into a Float with fromIntegral which is a really general function for turning number types into one another. (see Get sqrt from Int in Haskell)

isprime' :: Int -> Bool           
isprime' n | l == [] = True
           | otherwise = False
           where         
            asFloat :: Float -- new! - tell fromIntegral we want a float
            asFloat = fromIntegral n -- new! turn n into a Float
            l = [x|x<-[2..sqrt asFloat], mod n x == 0]

This also errors! but it's a new one!

test.hs:10:48: error:
    • Couldn't match expected type ‘Int’ with actual type ‘Float’
    • In the second argument of ‘mod’, namely ‘x’
      In the first argument of ‘(==)’, namely ‘mod n x’
      In the expression: mod n x == 0
   |
10 |             l = [x|x<-[2..sqrt asFloat], mod n x == 0]
   |                                                ^

this is saying that x is suddenly a Float. When we changed to [2..sqrt asFloat] we now have made a list of Floats ([Float]). We need to change that back to [Int]. we can do that by calling floor on the result of the square root.

isprime' :: Int -> Bool           
isprime' n | l == [] = True
           | otherwise = False
           where         
            asFloat :: Float
            asFloat = fromIntegral n 
            l = [x|x<-[2..floor (sqrt asFloat)], mod n x == 0] -- new! I added floor here to change the result of sqrt from a `Float` into a `Int`

This now correctly compiles.