Хаскелл Числовой Тип Разочарование

Question

У меня проблема с простой программой на Haskell. Предполагается, что число n-1 должно быть преобразовано в форму (2 ^ r) s, где n - число Кармайкла. Это на самом деле не относится к моему вопросу, но именно к этому стремится следующий набор функций.

divides::Int->Int->Bool
divides x y = not $ y `mod` x == 0

carmichaeltwos::Int->Int
carmichaeltwos n
    | not $ divides 2 n =0
    | otherwise = (+ 1) $ carmichaeltwos (n/2)

carmichaelodd::Int->Int
carmichaelodd n
    | not $ divides 2 n = n
    | otherwise = carmichaelodd (n/2)

factorcarmichael::Int->(Int, Int)
factorcarmichael n = (r, s)
    where
        nminus = n-1
        r = carmichaeltwos nminus
        s = carmichaelodd nminus

Когда я пытаюсь загрузить это в GHCi, Haskell выдает:

No instance for (Fractional Int)
  arising from a use of `/'
Possible fix: add an instance declaration for (Fractional Int)
In the first argument of `carmichaelodd', namely `(n / 2)'
In the expression: carmichaelodd (n / 2)
In an equation for `carmichaelodd':
    carmichaelodd n
      | not $ divides 2 n = n
      | otherwise = carmichaelodd (n / 2)

Я знаю, что функция / имеет тип (/): :( Fractional a) => a-> a-> a, но я не вижу, как исправить мою программу, чтобы это работало хорошо.

Кроме того, я понимаю, что я в основном вычисляю одно и то же дважды в функции factorcarmichael. Я не мог придумать простого способа, чтобы вычислить число за один проход и получить в качестве ответа нужный мне кортеж.

Answer 1

Чтобы разделить два Int с, когда вы знаете, как в данном случае, что дивиденд делится на делитель, используйте функцию div или quot, т.е. div n 2 или quot n 2. (div и quot отличаются только обработкой отрицательных операндов, когда «истинное» частное не является целым числом.)

Кроме того, почему вы определяете divides как not $ mod y x == 0? Если вы не используете нестандартное значение «деление», вы должны использовать просто mod y x == 0 - x деление y если y по модулю x равно нулю.

Что касается объединения carmichaeltwos и carmichaelodd, попробуйте использовать функцию until:

factorcarmichael n = until (\(_, s) -> not $ divides 2 s)
                           (\(r, s) -> (r+1, div s 2))
                           (0, n-1)