This data type represents integers modulo m, equipped with useful instances.

For example, 3 :: Mod 10 stands for the class of integers congruent to \( 3 \bmod 10 \colon \ldots {−17}, −7, 3, 13, 23 \ldots \)

>>> :set -XDataKinds
>>> 3 + 8 :: Mod 10 -- 3 + 8 = 11 ≡ 1 (mod 10)
1

Note: Mod 0 has no inhabitants, eventhough \( \mathbb{Z}/0\mathbb{Z} \) is technically isomorphic to \( \mathbb{Z} \).

Instances

The canonical representative of the residue class, always between 0 and m-1 inclusively.

The canonical representative of the residue class, always between 0 and m-1 inclusively.

Linking type and value levels: extract modulo m as a value.

Linking type and value levels: extract modulo m as a value.

If an argument is coprime with the modulus, return its modular inverse. Otherwise return Nothing .

>>> :set -XDataKinds
>>> invertMod 3 :: Mod 10 -- 3 * 7 = 21 ≡ 1 (mod 10)
Just 7
>>> invertMod 4 :: Mod 10 -- 4 and 10 are not coprime
Nothing

Synonym of (^%) .

Drop-in replacement for ^ with much better performance. Negative powers are allowed, but may throw DivideByZero , if an argument is not coprime with the modulus.

>>> :set -XDataKinds
>>> 3 ^% 4 :: Mod 10 -- 3 ^ 4 = 81 ≡ 1 (mod 10)
1
>>> 3 ^% (-1) :: Mod 10 -- 3 * 7 = 21 ≡ 1 (mod 10)
7
>>> 4 ^% (-1) :: Mod 10 -- 4 and 10 are not coprime
(*** Exception: divide by zero

This type represents elements of the multiplicative group mod m, i.e. those elements which are coprime to m. Use isMultElement to construct.

Instances

Unwrap a residue.

Attempt to construct a multiplicative group element.

For elements of the multiplicative group, we can safely perform the inverse without needing to worry about failure.

This type represents residues with unknown modulo and rational numbers. One can freely combine them in arithmetic expressions, but each operation will spend time on modulo's recalculation:

>>> 2 `modulo` 10 + 4 `modulo` 15
(1 `modulo` 5)
>>> (2 `modulo` 10) * (4 `modulo` 15)
(3 `modulo` 5)
>>> import Data.Ratio
>>> 2 `modulo` 10 + fromRational (3 % 7)
(1 `modulo` 10)
>>> 2 `modulo` 10 * fromRational (3 % 7)
(8 `modulo` 10)

If performance is crucial, it is recommended to extract Mod m for further processing by pattern matching. E. g.,

case modulo n m of
 SomeMod k -> process k -- Here k has type Mod m
 InfMod{} -> error "impossible"

Constructors

Instances

Create modular value by representative of residue class and modulo. One can use the result either directly (via functions from Num and Fractional ), or deconstruct it by pattern matching. Note that modulo never returns InfMod .

Computes the inverse value, if it exists.

>>> invertSomeMod (3 `modulo` 10) -- because 3 * 7 = 1 :: Mod 10
Just (7 `modulo` 10)
>>> invertSomeMod (4 `modulo` 10)
Nothing
>>> import Data.Ratio
>>> invertSomeMod (fromRational (2 % 5))
Just 5 % 2

Drop-in replacement for ^ , with much better performance. When -O is enabled, there is a rewrite rule, which specialises ^ to powSomeMod .

>>> powSomeMod (3 `modulo` 10) 4
(1 `modulo` 10)

This class gives the integer associated with a type-level natural. There are instances of the class for every concrete literal: 0, 1, 2, etc.

Since: base-4.7.0.0

Minimal complete definition

natSing