Почему divMod округляет вниз, а не обеспечивает положительный остаток?

Евклидова теорема деления, с которой знакомы большинство студентов-математиков и Haskellers, говорится, что

Учитывая два целых числа a и b, с b & ne; 0 существуют единственные целые числа q и r такие, что a = bq + r и 0 & le; r < | Б |.

Это дает обычные определения фактора и остатка. Этот документ 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)

Код

Ответ 1