Haskell数字类型沮丧

Question

我遇到了一个简单的Haskell程序问题.它应该将数字n-1分解为形式(2 ^ r)s,其中n是Carmichael数.这与我的问题并不完全相关,但这是以下一系列功能的目的.

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)

我知道函数/有类型(/):((分数a)=> a-> a-> a,但是我没有看到如何修复我的程序以使其工作得很好.

另外,我意识到我基本上在factorcarmichael函数中计算了两次相同的东西.我想不出任何简单的方法来计算一次通过的数字并获得我想要的元组作为答案.

Answer 1

分隔两个Int此时你会知道,在这种情况下,分红是除数整除,使用div或quot功能,即,div n 2或quot n 2.(div和quot当"真"的商不是整数的差异仅在于在其处理负操作数.)

另外,你为什么定义divides为not $ mod y x == 0？除非你使用"divides"的非标准含义,否则你应该使用just mod y x == 0- xdivide yiff y modulo x为零.

至于合并carmichaeltwos和carmichaelodd,请尝试使用until功能:

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