haskell - 为什么 divMod 向下舍入而不是确保正余数？

Question

Euclidean division theorem ，大多数数学学生和Haskellers都熟悉，指出

Given two integers a and b, with b ≠ 0, there exist unique integers q and r such that a = bq + r and 0 ≤ r < |b|.

这给出了商和余数的传统定义。这个 1992 paper认为它们是用编程语言实现的最佳方法。那么，为什么 divMod总是将股息向负无穷大取整？

Exact difference between div and quot显示 divMod已经在 quotRem 上做了相当多的额外工作;似乎不太可能做到正确。

代码

我编写了以下欧几里德风格的实现 divMod基于 GHC.Base 中的实现.我很确定这是对的。

divModInt2 :: Int -> Int -> (Int, Int)
divModInt2 (I# x) (I# y) = case (x `divModInt2#` y) of
                        divModInt2# :: Int# -> Int# -> (# Int#, Int# #)

x# `divModInt2#` y#
 | (x# <# 0#) = case (x# +# 1#) `quotRemInt#` y# of
                    (# q, r #) -> if y# <# 0#
                                  then (# q +# 1#, r -# y# -# 1# #)
                                  else (# q -# 1#, r +# y# -# 1# #)
 | otherwise  = x# `quotRemInt#` y#

这不仅产生了令人愉快的欧几里得结果，而且实际上比 GHC 代码更简单。它显然最多执行两次比较(而不是 GHC 代码的四次)。

事实上，这很可能完全没有分支，而不需要比我更了解原语的人做太多工作。

无分支版本的要点(大概了解更多的人可以使其更高效)。

x `divMod` y = (q + yNeg, r - yNeg * y - xNeg)
  where
    (q,r) = (x + xNeg) `quotRem` y
    xNeg = fromEnum (x < 0)
    yNeg = xNeg*(2 * fromEnum (y < 0) - 1)

Answer 1

在这一点上，我会说向后兼容性。 (见@augustss 评论。)也许它可以在报告的下一个主要版本中改变，但你必须说服haskell-prime 委员会，可能还有GHC 开发人员。