Я не понимаю число конверсий в Haskell

Вот что я пытаюсь сделать:

isPrime :: Int -> Bool
isPrime x = all (\y -> x `mod` y /= 0) [3, 5..floor(sqrt x)]

(Я знаю, что я не проверяю деление на два - пожалуйста, проигнорируйте это.) Вот что я получаю:

No instance for (Floating Int)
  arising from a use of `sqrt'
Possible fix: add an instance declaration for (Floating Int)
In the first argument of `floor', namely `(sqrt x)'
In the expression: floor (sqrt x)
In the second argument of `all', namely `[3, 5 .. floor (sqrt x)]'

Я потратил буквально часы, пытаясь все, что я могу придумать, чтобы сделать этот список, используя какой-то вариант sqrt, включая ерунду, вроде

intSqrt :: Int -> Int
intSqrt x = floor (sqrt (x + 0.0))

Кажется, что (sqrt 500) работает отлично, но (sqrt x) настаивает на том, что x является плавающим (почему?), и нет никакой функции, которую я могу найти для преобразования Int в реальный (почему?).

Мне не нужен метод проверки примитивности, я хочу понять, как это исправить. Почему это так сложно?

Ответ 1

В отличие от большинства других языков, Haskell отличает строго между целыми и плавающими типами и не будет конвертировать одно в другое неявно. См. здесь о том, как сделать преобразование явно. Там даже пример sqrt: -)

Основная причина этого заключается в том, что комбинация неявных преобразований и система классов Haskel (довольно сложная, но очень классная) очень затрудняли бы реконструкцию типа - возможно, она расширила бы ее за пределы того, где она может быть выполнена машинами в все. Разработчики языка чувствовали, что получение классов классов для арифметики стоит того, чтобы явно указывать преобразования.

Ответ 2

Ваша проблема в том, что, хотя вы пытались исправить ее разными способами, вы не пытались сделать что-то x, и именно там ваша проблема. Посмотрим на тип sqrt:

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

С другой стороны, x является Int, и если мы запросим GHCi для информации о Floating, он сообщает нам:

Prelude> :info Floating
class (Fractional a) => Floating a where
  pi :: a
  <...snip...>
  acosh :: a -> a
    -- Defined in GHC.Float
instance Floating Float -- Defined in GHC.Float
instance Floating Double -- Defined in GHC.Float

Таким образом, единственными типами Floating являются Float и Double s. Нам нужен способ преобразования Int в Double, так как floor :: (RealFrac a, Integral b) => a -> b переходит в другое направление. Всякий раз, когда у вас есть такой тип вопросов, вы можете спросить Hoogle, поисковую систему Haskell, которая ищет типы. К сожалению, если вы ищете Int -> Double, вы получите паршивые результаты. Но что, если мы расслабимся, что мы ищем? Если мы ищем Integer -> Double, мы обнаружим, что существует функция fromInteger :: Num a => Integer -> a, что почти точно то, что вы хотите. И если мы расслабляем наш тип до (Integral a, Num b) => a -> b, вы обнаружите, что существует функция fromIntegral :: (Integral a, Num b) => a -> b.

Таким образом, чтобы вычислить квадратный корень из целого числа, используйте floor . sqrt $ fromIntegral x или используйте

isqrt :: Integral i => i -> i
isqrt = floor . sqrt . fromIntegral

Вы думали о проблеме в правильном направлении для вывода sqrt; он вернул число с плавающей запятой, но вам нужно целое число. Однако в Haskell нет понятия подтипирования или неявных отбросов, поэтому вам нужно также изменить ввод на sqrt.

Чтобы решить некоторые другие проблемы:

intSqrt :: Int -> Int
intSqrt x = floor (sqrt (x + 0.0))

Вы называете это "глупостью", поэтому ясно, что вы не ожидаете, что это сработает, но почему? Проблема в том, что (+) имеет тип Num a => a -> a -> a - вы можете добавлять только две вещи одного типа. Это, как правило, хорошо, поскольку это означает, что вы не можете добавить комплексное число в реальную матрицу размером 5 × 5; однако, поскольку 0.0 должен быть экземпляром Fractional, вы не сможете добавить его в x :: Int.

Кажется, что (sqrt 500) отлично работает...

Это работает, потому что тип 500 не тот, который вы ожидаете. Позвольте спросить нашего надежного компаньона GHCi:

Prelude> :t 500
500 :: (Num t) => t

Фактически, все целочисленные литералы имеют этот тип; они могут быть любым числом, которое работает, потому что класс Num содержит функцию fromInteger :: Integer -> a. Поэтому, когда вы написали sqrt 500, GHC понял, что 500 необходимо удовлетворить 500 :: (Num t, Floating t) => t (и он будет неявно выбирать Double для таких числовых типов, как благодаря правилам по умолчанию). Аналогично, 0.0 выше имеет тип Fractional t => t, благодаря функции Fractional fromRational :: Rational -> a.

... но (sqrt x) настаивает на том, что x является плавающим...

См. выше, где мы смотрим на тип sqrt.

... и нет никакой функции, которую я могу найти для преобразования Int в реальный....

Ну, теперь у вас есть один: fromIntegral. Я не знаю, почему ты не смог найти его; по-видимому, Hoogle дает гораздо худшие результаты, чем я ожидал, благодаря родовому типу функции.

Почему это так сложно?

Надеюсь, что это уже не так, теперь у вас есть fromIntegral.