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

Question

大多数数学学生和Haskeller都熟悉的欧几里德分裂定理表明了这一点

给定两个整数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 开发人员。