haskell - 使用平方根查找素数的函数的正确类型注释是什么？

Question

为了提高检查一个数是否为素数的执行时间，我尝试使用高达 n 平方根的理解列表。运行代码时，它会抛出与未指定变量类型相关的错误(我得到的更少但未能修复)。我得到的最初建议是将 Integer 类型作为输入，将 Bool 作为输出。但是，我尝试使用“辅助”函数来获取所有因子，然后使用 isPrime 函数来检查 n 是否为素数。
这是代码行:

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

这是运行上一行后的错误

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

Answer 1

问题是 sqrt :: Floating a => a -> a 需要 n 的类型成为 Floating 的一个实例而 mod :: Integral a => a -> a -> a 要求它是 Integral .
虽然从技术上讲，可以制作一种既是 Floating 成员的类型。和 Integral类型类，它没有多大意义，因为 Integral要求类型跨越一组整数，并且应该可以转换为 Integer , 而 Floating意味着它应该能够捕获三角函数和双曲函数的结果，例如 sqrt , sin ， 等等。
一个简单的解决方法是创建一个计算积分平方根的函数，例如:

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

然后将其用于:

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

对于 100我们得到以下分隔符:

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

这里是我们的 isqrt可能仍然对舍入错误很敏感，因此最好实现一种算法，在整数域中完成所有工作。我把它留作练习。