haskell - 与类型相关的奇怪错误

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

您的问题出在调用sqrt x 。要了解原因，让我们检查 isPrime 的类型在 GHCi 中:

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 的输入可以是作为所有三个指定类型类的实例的任何类型。换句话说，一个数字同时是整数和实 float 。虽然原则上可以声明这样一种类型，但它没有多大意义；事实上，这种类型并不存在。

现在这解释了你的两个错误。第一个错误是 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 。果然，Hoogle 提出了更通用的 fromIntegral :: (Integral a, Num b) => a -> b ;将其插入 x 之前在 sqrt 的参数中会解决你的问题，因为你只会对待 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类型签名!但无论如何，这可能是个好主意。