Какова сигнатура типа этой функции Haskell?

Question

Я написал функцию для проверки, является ли число простым или нет:

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

Я не могу понять, какой должна быть сигнатура типа этой функции. Сначала я подумал, что это должно быть так:

prime :: Integral a => a -> Bool

Но тогда я получаю ошибки при компиляции, потому что sqrt ожидает Floating a и floor ожидает RealFrac a вместо 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)

Как я могу заставить эту функцию работать?

Answer 1

Проблема в том, что вы используете sqrt на n, что заставляет n быть числом с плавающей точкой; и вы также используете mod на 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

Answer 2

В качестве альтернативы, вы можете изменить верхний предел теста:

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

Кстати, вам не нужно n в качестве аргумента prime', так как он постоянен во всех вызовах.

Answer 3

Просто чтобы перейти к последнему биту, который не охватили другие ответы ...

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

Проверщик типов предположил, что prime может принимать аргумент типа a, если a является экземпляром классов Integral, RealFrac и Floating одновременно.

*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)

Однако, когда вы спрашиваете у него prime 5, он жалуется, что ни один из типов 5 по умолчанию не может удовлетворить эти условия.

Вполне возможно, что вы могли бы написать свой собственный

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 ...

(и вам также нужно будет добавить Num, Ord, Real, Fractional и т. Д.), И тогда prime 5 будет приемлемым, поскольку существует 5 :: Either Integer Float который удовлетворяет условиям типа.

Answer 4

Вы можете изменить (sqrt n) на (sqrt (fromInteger n)), чтобы заставить функцию работать должным образом. Это необходимо, потому что тип sqrt:

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

поэтому неправильно, например, делать:

sqrt (2 :: Int)