这个Haskell函数的类型签名是什么？

I wrote a function to check whether a number is prime or not:

我写了一个函数来检查数字是否为素数:

prime n = prime' n 2 (floor (sqrt n))
     where prime' n c u | n `mod` c == 0 = False
                        | c > u = True
                        | otherwise = prime' n (c+1) u

I can't figure out what the type signature of this function should be. At first I thought it should be this:

我无法弄清楚这个函数的类型签名应该是什么。起初我认为它应该是这样的:

prime :: Integral a => a -> Bool

But then I get errors when compiling because sqrt expects a Floating a and floor expects a RealFrac a instead of an Integral a. When I remove the type signature, it compiles, but the function does not work:

但是在编译时我会遇到错误,因为sqrt期望浮动a和floor需要RealFrac而不是Integral a。当我删除类型签名时,它会编译,但该函数不起作用:

*Euler> :t prime
prime :: (Integral a, RealFrac a, Floating a) => a -> Bool
*Euler> prime 5

<interactive>:1:0:
    Ambiguous type variable `t' in the constraints:
      `Floating t' arising from a use of `prime' at <interactive>:1:0-6
      `RealFrac t' arising from a use of `prime' at <interactive>:1:0-6
      `Integral t' arising from a use of `prime' at <interactive>:1:0-6
    Probable fix: add a type signature that fixes these type variable(s)

How can I make this function work?

如何使此功能起作用?

4 个解决方案

#1

The problem is that you use sqrt on n, which forces n to be a floating-point number; and you also use mod on n, which forces n to be an integer. Intuitively, from looking at your code, n should be an integer, so you can't directly call sqrt on it. Instead, you can use something like fromIntegral to convert it from an integer into another numeric type.

问题是你在n上使用sqrt,这迫使n成为一个浮点数;你还使用mod on n,它强制n为整数。直观地说,从查看代码开始,n应该是一个整数,因此您无法直接在其上调用sqrt。相反,您可以使用fromIntegral之类的东西将其从整数转换为另一种数字类型。

prime :: (Integral a) => a -> Bool
prime n = prime' n 2 (floor (sqrt (fromIntegral n)))
     where prime' n c u | n `mod` c == 0 = False
                        | c > u = True
                        | otherwise = prime' n (c+1) u

#2

Just to go over one last bit that the other answers haven't covered...

只是为了最后一点,其他答案没有涵盖......

*Euler> :t prime
prime :: (Integral a, RealFrac a, Floating a) => a -> Bool

The typechecker has inferred that prime can take an argument of type a as long as a is an instance of the Integral, RealFrac, and Floating classes all at once.

类型检查器推断,只要a是一个Integral,RealFrac和Floating类的实例,prime就可以采用类型a的参数。

*Euler> prime 5

<interactive>:1:0:
    Ambiguous type variable `t' in the constraints:
      `Floating t' arising from a use of `prime' at <interactive>:1:0-6
      `RealFrac t' arising from a use of `prime' at <interactive>:1:0-6
      `Integral t' arising from a use of `prime' at <interactive>:1:0-6
    Probable fix: add a type signature that fixes these type variable(s)

When you ask it to prime 5, however, it complains that none of the default types of 5 can satisfy those conditions.

但是,当你要求它为5时,它抱怨没有任何默认类型5可以满足这些条件。

It's quite possible that you could write your own

你很可能自己编写

instance (Integral a, RealFrac b, Floating b) => Integral (Either a b) where ...
instance (Integral a, RealFrac b, Floating b) => RealFrac (Either a b) where ...
instance (Integral a, RealFrac b, Floating b) => Floating (Either a b) where ...

(and you'd also have to add Num, Ord, Real, Fractional, etc. instances), and then prime 5 would be acceptable, since there would exist a 5 :: Either Integer Float which does satisfy the type conditions.

(并且你还必须添加Num,Ord,Real,Fractional等实例),然后prime 5是可以接受的,因为存在一个满足类型条件的5 :: Either Integer Float。

#3

Alternatively, you could change the upper-bound test:

或者,您可以更改上限测试:

prime n = prime' n 2
    where prime' n c | n `mod` c == 0 = False
                     | c * c > n = True
                     | otherwise = prime' n (c+1)

Btw, you don't need n as an argument to prime' since it is constant through all calls.

顺便说一下,你不需要n作为一个参数来填充'因为它在所有的调用中是不变的。

#4

You can change (sqrt n) to (sqrt (fromInteger n)) to make the function work as expected. This is needed because the type of sqrt is:

您可以将(sqrt n)更改为(sqrt(fromInteger n))以使函数按预期工作。这是必需的,因为sqrt的类型是:

sqrt :: (Floating a) => a -> a

so it is wrong, for example, to do:

所以这是错误的,例如:

sqrt (2 :: Int)

#1

prime :: (Integral a) => a -> Bool
prime n = prime' n 2 (floor (sqrt (fromIntegral n)))
     where prime' n c u | n `mod` c == 0 = False
                        | c > u = True
                        | otherwise = prime' n (c+1) u

#2