奇怪的与类型相关的错误

Question

我写了以下程序：

isPrime x = and [x `mod` i /= 0 | i <- [2 .. truncate (sqrt x)]]

primes = filter isPrime [1 .. ]

它应该构造质数列表。但是我得到了这个错误：

[1 of 1] Compiling Main             ( 7/main.hs, interpreted )

7/main.hs:3:16:
    Ambiguous type variable `a' in the constraints:
      `Floating a' arising from a use of `isPrime' at 7/main.hs:3:16-22
      `RealFrac a' arising from a use of `isPrime' at 7/main.hs:3:16-22
      `Integral a' arising from a use of `isPrime' at 7/main.hs:3:16-22
    Possible cause: the monomorphism restriction applied to the following:
      primes :: [a] (bound at 7/main.hs:3:0)
    Probable fix: give these definition(s) an explicit type signature
                  or use -XNoMonomorphismRestriction
Failed, modules loaded: none.

如果我显式指定isPrime函数的签名：

isPrime :: Integer -> Bool
isPrime x = and [x `mod` i /= 0 | i <- [2 .. truncate (sqrt x)]]

我甚至不能编译isPrime函数：

[1 of 1] Compiling Main             ( 7/main.hs, interpreted )

7/main.hs:2:45:
    No instance for (RealFrac Integer)
      arising from a use of `truncate' at 7/main.hs:2:45-61
    Possible fix: add an instance declaration for (RealFrac Integer)
    In the expression: truncate (sqrt x)
    In the expression: [2 .. truncate (sqrt x)]
    In a stmt of a list comprehension: i <- [2 .. truncate (sqrt x)]

7/main.hs:2:55:
    No instance for (Floating Integer)
      arising from a use of `sqrt' at 7/main.hs:2:55-60
    Possible fix: add an instance declaration for (Floating Integer)
    In the first argument of `truncate', namely `(sqrt x)'
    In the expression: truncate (sqrt x)
    In the expression: [2 .. truncate (sqrt x)]
Failed, modules loaded: none.

你能帮我理解为什么我会得到这些错误吗？

Answer 1

您的问题出在call sqrt x。要了解原因，让我们检查一下GHCi中的isPrime类型：

Prelude> let isPrime x = and [x `mod` i /= 0 | i <- [2 .. truncate (sqrt x)]]
Prelude> :t isPrime
isPrime :: (Integral a, Floating a, RealFrac a) => a -> Bool

这告诉我们，isPrime的输入可以是作为所有三个指定类型类的实例的任何类型。换句话说，一个同时是整数和实数浮点数的数。虽然原则上可以声明这样的类型，但它没有多大意义；事实上，并不存在这样的类型。

现在，这解释了你的两个错误。第一个错误是说isPrime在没有类型签名的情况下过于多态。monomorphism restriction规定(粗略地)如果通过模式匹配(比如f =或Just x =，而不是g y =)定义一个值，那么它在类型类中不能是多态的。因此，由于您没有为primes指定类型签名，因此它会推断出类型primes :: (Integral a, RealFrac a, Floating a) => [a]，然后因为它是多态的类型类而发出警告。

第二个错误来自您设置的三个类型类约束。mod说x的类型必须是Integral的实例；sqrt说它的输入必须是Floating的实例；truncate说sqrt的结果必须是RealFrac的实例。由于这些类型都用于实现相同的类型变量，因此x必须一次拥有所有这些类型，而且Integer既不是Floating的实例，也不是RealFrac的实例。因此，当您指定isPrime :: Integer -> Bool时，您会得到一个错误，因为Integer需要是Floating的实例，但不是。要解决这个问题，我们可以在Hoogle中搜索a conversion function of type (Integral a, Floating b) => a -> b。果然，胡格尔提出了更通用的fromIntegral :: (Integral a, Num b) => a -> b；在sqrt的参数中的x之前插入它可以解决您的问题，因为您只会将x视为Integral的一个实例。这为您提供了：

-- The one other change I made: only positive numbers are prime, and 1 is not a
-- prime.
isPrime :: Integral i => i -> Bool
isPrime x | x <= 1    = False
          | otherwise = and [ x `mod` i /= 0
                              | i <- [2..truncate . sqrt $ fromIntegral x] ]

primes :: [Integer]
primes = filter isPrime [2..]

请注意，由于单态限制，您仍然需要为primes提供类型签名！但不管怎样，这可能是一个好主意。

Answer 2

isPrime x= and [x mod i /= 0|i <- 2..截断(sqrt (fromIntegral x))]

在sqrt的参数中缺少从整型到浮点型的转换。