奇怪的类型相关的错误

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.要了解原因,让我们检查一下isPrimeGHCi中的类型:

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没有类型签名就太多态了.该单态限制说(大致),如果你(比如通过模式匹配定义的值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搜索类型的转换函数(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类型签名!但无论如何,这可能是一个好主意.