Copyright | (c) 2017 Andrew Lelechenko |
---|---|

License | MIT |

Maintainer | Andrew Lelechenko <andrew.lelechenko@gmail.com> |

Stability | Provisional |

Portability | Non-portable (GHC extensions) |

Safe Haskell | None |

Language | Haskell2010 |

Safe modular arithmetic with modulo on type level.

- data Mod (m :: Nat)
- getVal :: KnownNat m => Mod m -> Integer
- getNatVal :: KnownNat m => Mod m -> Natural
- getMod :: KnownNat m => Mod m -> Integer
- getNatMod :: KnownNat m => Mod m -> Natural
- invertMod :: KnownNat m => Mod m -> Maybe (Mod m)
- powMod :: (KnownNat m, Integral a) => Mod m -> a -> Mod m
- (^%) :: (KnownNat m, Integral a) => Mod m -> a -> Mod m
- data SomeMod where
- modulo :: Integer -> Natural -> SomeMod
- invertSomeMod :: SomeMod -> Maybe SomeMod
- powSomeMod :: Integral a => SomeMod -> a -> SomeMod
- class KnownNat (n :: Nat)

# Known modulo

Wrapper for residues modulo `m`

.

`Mod 3 :: Mod 10`

stands for the class of integers, congruent to 3 modulo 10 (…−17, −7, 3, 13, 23…).
The modulo is stored on type level, so it is impossible, for example, to add up by mistake
residues with different moduli.

> (3 :: Mod 10) + (4 :: Mod 12) error: Couldn't match type ‘12’ with ‘10’... > (3 :: Mod 10) + 8 (1 `modulo` 10)

Note that modulo cannot be negative.

getVal :: KnownNat m => Mod m -> Integer Source #

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

inclusively.

getNatVal :: KnownNat m => Mod m -> Natural Source #

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

inclusively.

getMod :: KnownNat m => Mod m -> Integer Source #

Linking type and value levels: extract modulo `m`

as a value.

getNatMod :: KnownNat m => Mod m -> Natural Source #

Linking type and value levels: extract modulo `m`

as a value.

invertMod :: KnownNat m => Mod m -> Maybe (Mod m) Source #

Computes the modular inverse, if the residue is coprime with the modulo.

> invertMod (3 :: Mod 10) Just (7 `modulo` 10) -- because 3 * 7 = 1 :: Mod 10 > invertMod (4 :: Mod 10) Nothing

powMod :: (KnownNat m, Integral a) => Mod m -> a -> Mod m Source #

Drop-in replacement for `^`

, with much better performance.

> powMod (3 :: Mod 10) 4 (1 `modulo` 10)

# Unknown modulo

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) > 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"

modulo :: Integer -> Natural -> SomeMod infixl 7 Source #

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`

.

invertSomeMod :: SomeMod -> Maybe SomeMod Source #

Computes the inverse value, if it exists.

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

powSomeMod :: Integral a => SomeMod -> a -> SomeMod Source #

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)