GHC.Natural.remNatural lacks a bang
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 product
s 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