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)

我知道函数/的类型为(/)::(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)