haskell - 使用重复减法的haskell模函数

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

除了完成工作的那行之外mod' x y | x >= y = (mod' (x-y) y)，您还扮演了两个参数的角色；mod' x y表示“x mod'y , the remainder on dividingx y” by。

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==0then since _ * 0is 0，x `mod` 0则应该x使方程式起作用。然而，这假设一个非严格的*，因为x `div` y是error "divide by zero"。在 Haskell 中，*是严格的，所以这个等式无论如何都不能成立。也许最好警告用户他们进行了涉及除以零的计算，而不是默默地继续，给

mod' _ 0 = error "division by zero"

无论如何，mod应该如何处理负数？

好的，主要是因为它是余数，x `mod` y应该在y和零之间，而不等于y，所以我们可以这样计算7 `mod` 3：

那么如果我们看一些东西mod (-3)呢？现在“介于y和零之间”意味着余数应该是负数，所以我们可以这样计算(-7) `mod` (-3)：

当然，减三和加三是一样的，但重点是我们得到相同的计算和答案，只是符号的变化：

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

在这两种情况下，符号x和y匹配。如果它们不同怎么办？首先，我们可以有积极的y：

其次，我们可能有负面y：

我们可以看到，方法不同，但是符号规则的变化

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

仍然站立。

那么我们应该对函数做些什么呢？

第 0 步：检查零第 1 步：检查负数y。如果是这样，请使用更改符号规则。
第二步：检查阳性x。如果是这样的话，y直到你下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

表明我们的逻辑是正确的。

Answer 2

otherwise = y

这是错误的：当x < y, x mod y == x.

另外，不x `mod` 0应该是错误吗？

编辑：而且mod' 0 x = 0，不是x。