mod
Modular arithmetic,
promoting moduli to the type level, with an emphasis on performance.
Originally a part of arithmoi package.
> :set XDataKinds
> 4 + 5 :: Mod 7
(2 `modulo` 7)
> 4  5 :: Mod 7
(6 `modulo` 7)
> 4 * 5 :: Mod 7
(6 `modulo` 7)
> 4 / 5 :: Mod 7
(5 `modulo` 7)
> 4 ^ 5 :: Mod 7
(2 `modulo` 7)
Competitors
There are other Haskell packages, employing the very same idea of moduli on the type level,
namely modular
and modulararithmetic
. Unfortunately, both of them fall behind
in terms of performance. Here is a brief comparison:
Discipline 
mod 
modular 
modulararithmetic 
Addition 
Fast 
Slow 
Slow 
Small (*) 
Fast 
Slow 
Slow 
Inversion 
Fast 
N/A 
Slow 
Power 
Fast 
Slow 
Slow 
Overflows 
Safe 
Safe 
Unsafe 

Addition.
It appears that modular
and modulararithmetic
implementations of
the modular addition involve divisions, while mod
completely avoids
this costly operation. It makes difference even for small numbers;
e. g., sum [1..10^7]
becomes 5x faster. For larger integers the speed up
is even more significant, because the computational complexity of division is not linear.

Small (*)
.
When a modulo fits a machine word (which is quite a common case on 64bit architectures),
mod
implements the modular multiplication as a couple of CPU instructions
and neither allocates intermediate arbitraryprecision values,
nor calls libgmp
at all. For computations like product [1..10^7]
this gives a 3x boost to performance
in comparison to other libraries.

Inversion.
This package relies on libgmp
for modular inversions.
Even for small arguments it is about 5x faster than
the native implementation of modular inversion
in modulararithmetic
.

Power.
This package relies on libgmp
for modular exponentiation.
Even for small arguments it is about 2x faster than competitors.

Overflows.
At first glance modulararithmetic
is more flexible than mod
,
because it allows to specify the underlying representation of a modular residue,
e. g., Mod Integer 100
, Mod Int 100
, Mod Word8 100
. We argue that this is
a dangerous freedom, vulnerable to overflows.
For instance, 20 ^ 2 :: Mod Word8 100
returns 44
instead of expected 0
.
Even less expected is that 50 :: Mod Word8 300
appears to be 6
(remember that typelevel numbers are always Natural
).
Citius, altius, fortius!
If you are looking for an ultimate performance
and your moduli fit into Word
,
try Data.Mod.Word
,
which is a dropin replacement of Data.Mod
,
but offers 3x faster addition,
2x faster multiplication and much less allocations.
Whatâ€™s next?
This package was cut out of arithmoi
to provide a modular arithmetic
with a light dependency footprint. This goal certainly limits the scope of API
to the bare minimum. If you need more advanced tools
(the Chinese remainder theorem, cyclic groups, modular equations, etc.)
please refer to Math.NumberTheory.Moduli.