使用重複減法的哈斯克爾模量函數

Question

我需要編寫一個模數函數（使用重複減法而不使用原語mod函數）。

mod' :: Int -> Int -> Int 
mod' x 0 = 0 
mod' 0 x = x 
mod' x y | x >= y = (mod' (x-y) y) 
     | otherwise = y 

我這樣做，但是這是行不通的。它編譯，但我得到這樣的不正確的答案：

*Main> 7 `mod'` 4 
4 
*Main> 3 `mod'` 5 
5 

什麼是錯？

Answer 1

otherwise = y

這是錯誤的：當x < y，x mod y == x。

另外，不應該x `mod` 0是一個錯誤？

編輯：而且，mod' 0 x = 0，而不是x。

Answer 2

除了做這項工作的線，mod' x y | x >= y = (mod' (x-y) y)，你有兩個參數轉置的角色; mod' x y表示``x mod' y , the remainder on dividing x by y`。

mod' :: Int -> Int -> Int 
mod' x 0 = x 
mod' 0 x = 0 
mod' x y | x >= y = (mod' (x-y) y) 
     | otherwise = x 

零

div和mod來自方程

x = (x `div` y) * y + (x `mod` y) 

你可以爭辯說，如果y==0那麼因爲_ * 0是0，x `mod` 0應該x使方程的工作。 但是這假定非嚴格的*，因爲x `div` y是​​。在Haskell中，*是嚴格的，所以方程式無論如何都會崩潰。也許這是更好地警告他們確實是零，而不是默默的走在前面，涉及部門的計算，用戶，給

mod' _ 0 = error "division by zero" 

國防部應該如何爲負數的工作呢？

OK，更主要的是，因爲它是一個餘數，x `mod` y應該是y和零，不等於y之間，因此，我們可以計算出7 `mod` 3這樣的：

好如果我們看一下mod (-3)怎麼辦？現在，「y和零之間」是指其餘的應該是否定的，那麼我們可以計算(-7) `mod` (-3)這樣：

當然，考慮減三是一樣增加3，但主要的一點是，我們得到了同樣的計算和答案，只是符號變化：

(-x) `mod` (-y) = -(x `mod` y) 

在這兩個情況下，x和y相匹配的標誌。如果它們有區別呢？首先，我們可以有積極的y：

其次，我們可以有負y：

正如我們所看到的，方法是不同的，但跡象規則

的變化

(-x) `mod` (-y) = -(x `mod` y) 

仍然存在。

那麼我們應該怎麼做的功能？

步驟0：檢查零點 步驟1：檢查否定的y。如果是，請使用符號規則的更改。
第2步：檢查積極的x。如果是這樣的話，直到y。
步驟3：否則，添加y，直到您超過零。

在代碼中，這是

mod' :: Int -> Int -> Int 
mod' x 0 = error "mod by zero" 
mod' 0 x = 0 
mod' x y | y < 0 = - (mod' (-x) (-y)) 
     | x > 0 = modpos x 
     | otherwise = modneg x 
where 
    modpos x | x < y = x 
      | otherwise = modpos (x-y) 
    modneg x | x >= 0 = x 
      | otherwise = modneg (x+y) 

和快速檢查：

ghci> all id [x `mod` y == x `mod'` y | x <- [-10 .. 10], y<- [-10 .. 10],y/=0] 
True 

表明我們得到了正確的邏輯。