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

Question

大多数数学学生和Haskellers都熟悉的欧几里得除法定理指出：

给定两个整数 a 和 b，其中 b ≠ 0，存在唯一整数 q 和 r，使得 a = bq + r 且 0 ≤ r < |b|。

这给出了商和余数的传统定义。这篇1992 年的论文认为它们是用编程语言实现的最佳方法。那么，为什么divMod总是将红利四舍五入到负无穷呢？

div 和 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 开发人员。