What are the correct type annotations for a function to find prime numbers using square root?

user_15094799 0
Viewed 62

In order to improve the execution time checking whether a number is prime, I am trying to use a comprehension list up to the square root of n. When running the code, it's throwing errors related to not specifying a variable type (That I more less get but failed to fix). The initial advice I got was to have an Integer type as input and a Bool as output. However, I was trying to have a 'helper' function to get all the factors and then have the isPrime function to check whether n was prime.

This is the line of code:

isPrime n = [x | x <- [2..sqrt n], n `mod` x == 0]

This is the error after running the previous line

isPrime 100
<interactive>:12:1: error:
    * Ambiguous type variable `a0' arising from a use of `print'
      prevents the constraint `(Show a0)' from being solved.
      Probable fix: use a type annotation to specify what `a0' should be.
      These potential instances exist:
        instance Show Ordering -- Defined in `GHC.Show'
        instance Show Integer -- Defined in `GHC.Show'
        instance Show a => Show (Maybe a) -- Defined in `GHC.Show'
        ...plus 22 others
haskell
1 Answers

The problem is that sqrt :: Floating a => a -> a requires the type of n to be an instance of Floating whereas mod :: Integral a => a -> a -> a requires it to be Integral.

While technically speaking one can make a type that is both a member of the Floating and Integral type class, it does not make much sense, since Integral requires the type to span a set of integral numbers and should be convertable to an Integer, whereas Floating means it should be able to capture the results of trigonometric and hyperbolic functions like sqrt, sin, etc.

An easy fix is to make a function that calculates the integral square root, for example:

isqrt :: Integral a => a -> a
isqrt = ceiling . (sqrt :: Double -> Double) . fromIntegral

and then use this with:

isPrime :: Integral a => a -> [a]
isPrime n = [x | x <- [2..isqrt n], n `mod` x == 0]

For 100 we get the following dividers:

Prelude> isPrime 100
[2,4,5,10]

Here our isqrt might still be sensitive to rounding errors, so it might be better to implement an algorithm that will do all the work in integer land. I leave that as an exercise.

user_675790
Related