与 Haskell 类型系统作斗争

Question

我正在尝试通过在特定情况下执行基本任务来学习一些 Haskell 我正在尝试实现一些用于素数检查的基本功能，但我真的可以弄清楚类型，我的代码是

isPrime :: (Num a) => a -> Bool
isPrime n
    | n <= 1 = False
    | otherwise = not $ 0 `elem` map (mod n) [2..m] where m = floor $ sqrt n

我尝试使用不同的数字类型而不是 (Num a) => a 或将 sqrt 与 fromIntegral 一起使用，但我仍然收到错误消息，例如：

*Could not deduce (Floating a) arising from a use of `sqrt'
  from the context: Num a
    bound by the type signature for:
               isPrime :: forall a. Num a => a -> Bool
    at Helpers.hs:5:1-31
  Possible fix:
    add (Floating a) to the context of
      the type signature for:
        isPrime :: forall a. Num a => a -> Bool
* In the second argument of `($)', namely `sqrt n'
  In the expression: floor $ sqrt n
  In an equation for `m': m = floor $ sqrt n
| otherwise = not $ 0 `elem` map (mod n) [2..m] where m = floor $ sqrt n

我真的可以在这里得到一些帮助，提前谢谢你。

Answer 1

你的代码有两个问题：

不兼容的类型。

同时调用sqrt n和(mod n)需要n同时为Floating和Integral。

上下文不足。仅要求 (Num a) 不允许这两种操作。

一个可能的修复方法是：a) 将类型上下文缩小到更简洁的 (Integral a)； b) 将 fromIntegral 添加到 sqrt 的参数：

isPrime :: Integral a => a -> Bool
isPrime n
    | n <= 1 = False
    | otherwise = not $ 0 `elem` map (mod n) [2..m] where m = floor $ sqrt $fromIntegral n

Answer 2

正如其他人提到的，使用 mod 需要 a 为 Integral，使用 sqrt 需要 a Floating。从你的函数名称来看，我假设你想在整数类型上使用它。因此，您可以通过将签名更改为 isPrime :: (Integral a) => a -> Bool，然后将 sqrt 预合成为 fromIntegral 来解决此问题。你可以做类似

的事情

where m = floor . sqrt . fromIntegral $ n

另一种选择是将 [1..m] 替换为 takeWhile (\x -> x * x <= n) [1..] 之类的内容，以避免需要 Floating.

Answer 3

编译器描述的问题是您将不兼容的操作应用于同一类型：mod 需要 Integral a, sqrt requires Floating a，并且没有类型可以同时满足这两者。您可以使用 fromIntegral 和 ceiling 等类型转换来解决这个问题，但您需要小心避免舍入错误。对于我的测试，我删除了类型约束并使用 m = ceiling $ sqrt $ fromIntegral n，这导致了推断类型 isPrimeSqrt :: Integral a => a -> Bool。

另一种方法是考虑冲突发生的原因并寻找其他解决方案。 sqrt 的原因是为测试生成一个优化的停止点。我们可以用另一种方式找到那个停止点吗？

事实证明，虽然除法成本很高，但它经常会产生两个结果：商和余数。对于 mod，您正在寻找后者，但我们有 divMod and quotRem which produce both. So it could be worth testing if that's notably slower than the plain mod test (benchmark results，比较 [2..] 与 [2..m]）。

isPrime n = (n > 1) && null (filter isFactor (takeWhile notTooHigh divisors))
  where notTooHigh (divisor,quotient,_) = divisor <= quotient
        isFactor (_,_,remainder) = remainder == 0
        divisors = [(divisor,quotient,remainder) |
                    divisor <- 2:[3,5..],
                    let (quotient,remainder) = quotRem n divisor]

与 Haskell 类型系统作斗争

Struggling with Haskell type system

haskell

types

sqrt