mod-0.2.1.0: Fast type-safe modular arithmetic

Copyright | (c) 2017-2022 Andrew Lelechenko
License | MIT
Maintainer | Andrew Lelechenko <andrew.lelechenko@gmail.com>
Safe Haskell | None
Language | Haskell2010

Data.Mod

Description

Modular arithmetic, promoting moduli to the type level, with an emphasis on performance. Originally part of the arithmoi package.

This module supports moduli of arbitrary size. Use Data.Mod.Word to achieve better performance, when your moduli fit into `Word`.

Synopsis

- data Mod (m :: Nat)
- unMod :: Mod m -> Natural
- invertMod :: forall (m :: Nat). KnownNat m => Mod m -> Maybe (Mod m)
- (^%) :: forall (m :: Nat) a. (KnownNat m, Integral a) => Mod m -> a -> Mod m

# Documentation

data Mod (m :: Nat) Source #

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

Instances details

KnownNat m => Vector Vector (Mod m) Source # | No validation checks are performed; reading untrusted data may corrupt internal invariants.

Instance details

Defined in Data.Mod

Methods

basicUnsafeFreeze :: Mutable Vector s (Mod m) -> ST s (Vector (Mod m))

basicUnsafeThaw :: Vector (Mod m) -> ST s (Mutable Vector s (Mod m))

basicLength :: Vector (Mod m) -> Int

basicUnsafeSlice :: Int -> Int -> Vector (Mod m) -> Vector (Mod m)

basicUnsafeIndexM :: Vector (Mod m) -> Int -> Box (Mod m)

basicUnsafeCopy :: Mutable Vector s (Mod m) -> Vector (Mod m) -> ST s ()

elemseq :: Vector (Mod m) -> Mod m -> b -> b

KnownNat m => MVector MVector (Mod m) Source # | No validation checks are performed; reading untrusted data may corrupt internal invariants.

Instance details

Defined in Data.Mod

Methods

basicLength :: MVector s (Mod m) -> Int

basicUnsafeSlice :: Int -> Int -> MVector s (Mod m) -> MVector s (Mod m)

basicOverlaps :: MVector s (Mod m) -> MVector s (Mod m) -> Bool

basicUnsafeNew :: Int -> ST s (MVector s (Mod m))

basicInitialize :: MVector s (Mod m) -> ST s ()

basicUnsafeReplicate :: Int -> Mod m -> ST s (MVector s (Mod m))

basicUnsafeRead :: MVector s (Mod m) -> Int -> ST s (Mod m)

basicUnsafeWrite :: MVector s (Mod m) -> Int -> Mod m -> ST s ()

basicClear :: MVector s (Mod m) -> ST s ()

basicSet :: MVector s (Mod m) -> Mod m -> ST s ()

basicUnsafeCopy :: MVector s (Mod m) -> MVector s (Mod m) -> ST s ()

basicUnsafeMove :: MVector s (Mod m) -> MVector s (Mod m) -> ST s ()

basicUnsafeGrow :: MVector s (Mod m) -> Int -> ST s (MVector s (Mod m))

NFData (Mod m) Source # |
Instance details Defined in Data.Mod Methods rnf :: Mod m -> () Source #
KnownNat m => Bounded (Mod m) Source # |
Instance details Defined in Data.Mod Methods minBound :: Mod m Source # maxBound :: Mod m Source #
KnownNat m => Enum (Mod m) Source # |
Instance details Defined in Data.Mod Methods succ :: Mod m -> Mod m Source # pred :: Mod m -> Mod m Source # toEnum :: Int -> Mod m Source # fromEnum :: Mod m -> Int Source # enumFrom :: Mod m -> [Mod m] Source # enumFromThen :: Mod m -> Mod m -> [Mod m] Source # enumFromTo :: Mod m -> Mod m -> [Mod m] Source # enumFromThenTo :: Mod m -> Mod m -> Mod m -> [Mod m] Source #
KnownNat m => Storable (Mod m) Source # | No validation checks are performed; reading untrusted data may corrupt internal invariants.

Instance details

Defined in Data.Mod

Methods

sizeOf :: Mod m -> Int Source #

alignment :: Mod m -> Int Source #

peekElemOff :: Ptr (Mod m) -> Int -> IO (Mod m) Source #

pokeElemOff :: Ptr (Mod m) -> Int -> Mod m -> IO () Source #

peekByteOff :: Ptr b -> Int -> IO (Mod m) Source #

pokeByteOff :: Ptr b -> Int -> Mod m -> IO () Source #

peek :: Ptr (Mod m) -> IO (Mod m) Source #

poke :: Ptr (Mod m) -> Mod m -> IO () Source #

Generic (Mod m) Source # |

Instance details

Defined in Data.Mod

Associated Types

type Rep (Mod m) |
Instance details Defined in Data.Mod type Rep (Mod m) = D1 ('MetaData "Mod" "Data.Mod" "mod-0.2.1.0-LThBjChsXcIJTO5n60xW3f" 'True) (C1 ('MetaCons "Mod" 'PrefixI 'True) (S1 ('MetaSel ('Just "unMod") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 Natural)))

Methods

from :: Mod m -> Rep (Mod m) x Source #

to :: Rep (Mod m) x -> Mod m Source #

KnownNat m => Num (Mod m) Source # |
Instance details Defined in Data.Mod Methods (+) :: Mod m -> Mod m -> Mod m Source # (-) :: Mod m -> Mod m -> Mod m Source # (*) :: Mod m -> Mod m -> Mod m Source # negate :: Mod m -> Mod m Source # abs :: Mod m -> Mod m Source # signum :: Mod m -> Mod m Source # fromInteger :: Integer -> Mod m Source #
KnownNat m => Read (Mod m) Source # | Wrapping behaviour, similar to the existing `instance` `Read` `Int`.
Instance details Defined in Data.Mod Methods readsPrec :: Int -> ReadS (Mod m) Source # readList :: ReadS [Mod m] Source # readPrec :: ReadPrec (Mod m) Source # readListPrec :: ReadPrec [Mod m] Source #
KnownNat m => Fractional (Mod m) Source # | Division by a residue, which is not coprime with the modulus, throws `DivideByZero`. Consider using `invertMod` for non-prime moduli.
Instance details Defined in Data.Mod Methods (/) :: Mod m -> Mod m -> Mod m Source # recip :: Mod m -> Mod m Source # fromRational :: Rational -> Mod m Source #
KnownNat m => Real (Mod m) Source # |
Instance details Defined in Data.Mod Methods toRational :: Mod m -> Rational Source #
Show (Mod m) Source # |
Instance details Defined in Data.Mod Methods showsPrec :: Int -> Mod m -> ShowS Source # show :: Mod m -> String Source # showList :: [Mod m] -> ShowS Source #
Eq (Mod m) Source # |
Instance details Defined in Data.Mod Methods (==) :: Mod m -> Mod m -> Bool Source # (/=) :: Mod m -> Mod m -> Bool Source #
Ord (Mod m) Source # |
Instance details Defined in Data.Mod Methods compare :: Mod m -> Mod m -> Ordering Source # (<) :: Mod m -> Mod m -> Bool Source # (<=) :: Mod m -> Mod m -> Bool Source # (>) :: Mod m -> Mod m -> Bool Source # (>=) :: Mod m -> Mod m -> Bool Source # max :: Mod m -> Mod m -> Mod m Source # min :: Mod m -> Mod m -> Mod m Source #
KnownNat m => Prim (Mod m) Source # | No validation checks are performed; reading untrusted data may corrupt internal invariants.

Instance details

Defined in Data.Mod

Methods

sizeOfType# :: Proxy (Mod m) -> Int# Source #

sizeOf# :: Mod m -> Int# Source #

alignmentOfType# :: Proxy (Mod m) -> Int# Source #

alignment# :: Mod m -> Int# Source #

indexByteArray# :: ByteArray# -> Int# -> Mod m Source #

readByteArray# :: MutableByteArray# s -> Int# -> State# s -> (# State# s, Mod m #) Source #

writeByteArray# :: MutableByteArray# s -> Int# -> Mod m -> State# s -> State# s Source #

setByteArray# :: MutableByteArray# s -> Int# -> Int# -> Mod m -> State# s -> State# s Source #

indexOffAddr# :: Addr# -> Int# -> Mod m Source #

readOffAddr# :: Addr# -> Int# -> State# s -> (# State# s, Mod m #) Source #

writeOffAddr# :: Addr# -> Int# -> Mod m -> State# s -> State# s Source #

setOffAddr# :: Addr# -> Int# -> Int# -> Mod m -> State# s -> State# s Source #

KnownNat m => Euclidean (Mod m) Source # | `Mod` `m` is not even an integral domain for composite `m`, much less a Euclidean domain. The instance is lawful only for prime `m`, otherwise we try to do our best: ``quot` x y` returns any `z` such that `x == y * z`, `rem` is not always 0, and both can throw `DivideByZero`.
Instance details Defined in Data.Mod Methods quotRem :: Mod m -> Mod m -> (Mod m, Mod m) Source # quot :: Mod m -> Mod m -> Mod m Source # rem :: Mod m -> Mod m -> Mod m Source # degree :: Mod m -> Natural Source #
KnownNat m => Field (Mod m) Source # | `Mod` `m` is not even an integral domain for composite `m`, much less a field. The instance is lawful only for prime `m`, otherwise division by a residue, which is not coprime with the modulus, throws `DivideByZero`. Consider using `invertMod` for non-prime moduli.
Instance details Defined in Data.Mod
KnownNat m => GcdDomain (Mod m) Source # | `Mod` `m` is not even an integral domain for composite `m`, much less a GCD domain. However, `gcd` and `lcm` are still meaningful even for composite `m`, corresponding to a sum and an intersection of ideals. The instance is lawful only for prime `m`, otherwise ``divide` x y` tries to return any `Just z` such that `x == y * z`.
Instance details Defined in Data.Mod Methods divide :: Mod m -> Mod m -> Maybe (Mod m) Source # gcd :: Mod m -> Mod m -> Mod m Source # lcm :: Mod m -> Mod m -> Mod m Source # coprime :: Mod m -> Mod m -> Bool Source #
KnownNat m => Ring (Mod m) Source # |
Instance details Defined in Data.Mod Methods negate :: Mod m -> Mod m Source #
KnownNat m => Semiring (Mod m) Source # |
Instance details Defined in Data.Mod Methods plus :: Mod m -> Mod m -> Mod m Source # zero :: Mod m Source # times :: Mod m -> Mod m -> Mod m Source # one :: Mod m Source # fromNatural :: Natural -> Mod m Source #
KnownNat m => Unbox (Mod m) Source # | No validation checks are performed; reading untrusted data may corrupt internal invariants.
Instance details Defined in Data.Mod
newtype MVector s (Mod m) Source # | Unboxed vectors of `Mod` cause more nursery allocations than boxed ones, but reduce pressure on the garbage collector, especially for large vectors.
Instance details Defined in Data.Mod newtype MVector s (Mod m) = ModMVec (MVector s (Mod m))
type Rep (Mod m) Source # |
Instance details Defined in Data.Mod type Rep (Mod m) = D1 ('MetaData "Mod" "Data.Mod" "mod-0.2.1.0-LThBjChsXcIJTO5n60xW3f" 'True) (C1 ('MetaCons "Mod" 'PrefixI 'True) (S1 ('MetaSel ('Just "unMod") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 Natural)))
newtype Vector (Mod m) Source # | Unboxed vectors of `Mod` cause more nursery allocations than boxed ones, but reduce pressure on the garbage collector, especially for large vectors.
Instance details Defined in Data.Mod newtype Vector (Mod m) = ModVec (Vector (Mod m))

unMod :: Mod m -> Natural Source #

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

    >>> :set -XDataKinds
    >>> -1 :: Mod 10
    9

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

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

(^%) :: forall (m :: Nat) a. (KnownNat m, Integral a) => Mod m -> a -> Mod m infixr 8 Source #

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