GitLab

Summary

The existing implementation of GHC.Natural.remNatural makes an impression on GHC that it is lazy in the first argument. While this is technically true (division by 0 can throw an error without evaluation of dividend), I find this behaviour practically undesirable. Cf. GHC.Integer.Type.remInteger, which explicitly puts a bang to convince GHC that both arguments are used strictly:

remInteger :: Integer -> Integer -> Integer
remInteger !_       (S# 1#) = S# 0#
...

It is quite unexpected from user's viewpoint that changing Integer to Natural incurs profound time/memory degradation.

Steps to reproduce

import Numeric.Natural

newtype Mod a = Mod a deriving (Show)

instance Integral a => Num (Mod a) where
  Mod a * Mod b = Mod (a * b         `mod` 10000000019)
  fromInteger n = Mod (fromInteger n `mod` 10000000019)

main :: IO ()
main = do
  print $ product $ map Mod [(1 :: Integer) .. 100000000]
  print $ product $ map Mod [(1 :: Natural) .. 100000000]

$ ghc -O2 -rtsopts Main.hs
$ ./Main +RTS -M100M
Mod 3281139056
Main: Heap exhausted; ...

Expected behavior

I would expect that both products are computed within roughly same time/memory. But at the moment Natural-based version builds a chain of thunks and falls out-of-memory. I propose to bring GHC.Natural.remNatural in line with GHC.Integer.Type.remInteger by adding a bang:

remNatural :: Natural -> Natural -> Natural
remNatural !_         (NatS# 0##) = divZeroError
...

Environment

• GHC version used: 8.8.1