Haskell递归(没有(RealFrac Int)的实例，因为使用“round”)

Question

modPow :: Int -> Int -> Int -> Int  
-- Pre: 1 <= m <= sqrt(maxint)  
modPow x y n   
  |even y    = (((x^halfy) `mod` n)^2) `mod` n  
  |otherwise = (x `mod` n)*(x ^ (y-1) `mod` n) `mod` n  
    where halfy = round (y/2)  

终端报告：

Recursion.hs:39:19:  
    No instance for (RealFrac Int) arising from a use of ‘round’  
    In the expression: round (y / 2)  
    In an equation for ‘halfy’: halfy = round (y / 2)  
    In an equation for ‘modPow’:  
        modPow x y n  
          | even y = (((x ^ halfy) `mod` n) ^ 2) `mod` n  
          | otherwise = (x `mod` n) * (x ^ (y - 1) `mod` n) `mod` n  
          where  
              halfy = round (y / 2)  
Recursion.hs:39:27:  
    No instance for (Fractional Int) arising from a use of ‘/’  
    In the first argument of ‘round’, namely ‘(y / 2)’  
    In the expression: round (y / 2)  
    In an equation for ‘halfy’: halfy = round (y / 2) 

Answer 1

在halfy = round (y/2)中，你有y :: Int 。但是，(/)运算符是在 Fractional typeclass 中定义的（Int 不是它的实例;考虑一下哪个Int可以表示，例如 3/2）。

但是，还有整数除法运算符div和quot，它们将为您提供四舍五入的Int结果。因此，只需将halfy的定义替换为

halfy = y `quot` 2

这将恢复您的halfy行为，因为暂时忘记打字问题，y/2的小数部分始终为 0 或 0.5，并且round将两者四舍五入为 0：

Prelude> round (1/2) :: Int
0
Prelude> round (-1/2) :: Int
0
Prelude> 1 `quot` 2 :: Int
0
Prelude> (-1) `quot` 2 :: Int
0
Prelude> (-1) `div` 2 :: Int -- This doesn't recover the same behaviour for negative y!
-1