Data.Mod.Word

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

This module supports only moduli, which fit into Word. Use the (slower) Data.Mod module for handling arbitrary-sized moduli.

Documentation

data Mod (m :: Nat)

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

Vector Vector (Mod m)

No validation checks are performed; reading untrusted data may corrupt internal invariants.

Defined in Data.Mod.Word

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

MVector MVector (Mod m)

No validation checks are performed; reading untrusted data may corrupt internal invariants.

Defined in Data.Mod.Word

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

Storable (Mod m)

No validation checks are performed; reading untrusted data may corrupt internal invariants.

Defined in Data.Mod.Word

Methods

sizeOf :: Mod m -> Int

alignment :: Mod m -> Int

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

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

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

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

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

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

KnownNat m => Bounded (Mod m)

Defined in Data.Mod.Word

Methods

minBound :: Mod m

maxBound :: Mod m

KnownNat m => Enum (Mod m)

Defined in Data.Mod.Word

Methods

succ :: Mod m -> Mod m

pred :: Mod m -> Mod m

toEnum :: Int -> Mod m

fromEnum :: Mod m -> Int

enumFrom :: Mod m -> [Mod m]

enumFromThen :: Mod m -> Mod m -> [Mod m]

enumFromTo :: Mod m -> Mod m -> [Mod m]

enumFromThenTo :: Mod m -> Mod m -> Mod m -> [Mod m]

Generic (Mod m)

Defined in Data.Mod.Word

Associated Types

type Rep (Mod m) :: Type -> Type

Methods

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

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

KnownNat m => Num (Mod m)

Defined in Data.Mod.Word

Methods

(+) :: Mod m -> Mod m -> Mod m

(-) :: Mod m -> Mod m -> Mod m

(*) :: Mod m -> Mod m -> Mod m

negate :: Mod m -> Mod m

abs :: Mod m -> Mod m

signum :: Mod m -> Mod m

fromInteger :: Integer -> Mod m

KnownNat m => Read (Mod m)

Wrapping behaviour, similar to the existing instance Read Int.

Defined in Data.Mod.Word

Methods

readsPrec :: Int -> ReadS (Mod m)

readList :: ReadS [Mod m]

readPrec :: ReadPrec (Mod m)

readListPrec :: ReadPrec [Mod m]

KnownNat m => Fractional (Mod m)

Division by a residue, which is not coprime with the modulus, throws DivideByZero. Consider using invertMod for non-prime moduli.

Defined in Data.Mod.Word

Methods

(/) :: Mod m -> Mod m -> Mod m

recip :: Mod m -> Mod m

fromRational :: Rational -> Mod m

KnownNat m => Real (Mod m)

Defined in Data.Mod.Word

Methods

toRational :: Mod m -> Rational

Show (Mod m)

Defined in Data.Mod.Word

Methods

showsPrec :: Int -> Mod m -> ShowS

show :: Mod m -> String

showList :: [Mod m] -> ShowS

NFData (Mod m)

Defined in Data.Mod.Word

Methods

rnf :: Mod m -> ()

Eq (Mod m)

Defined in Data.Mod.Word

Methods

(==) :: Mod m -> Mod m -> Bool

(/=) :: Mod m -> Mod m -> Bool

Ord (Mod m)

Defined in Data.Mod.Word

Methods

compare :: Mod m -> Mod m -> Ordering

(<) :: Mod m -> Mod m -> Bool

(<=) :: Mod m -> Mod m -> Bool

(>) :: Mod m -> Mod m -> Bool

(>=) :: Mod m -> Mod m -> Bool

max :: Mod m -> Mod m -> Mod m

min :: Mod m -> Mod m -> Mod m

Prim (Mod m)

No validation checks are performed; reading untrusted data may corrupt internal invariants.

Defined in Data.Mod.Word

Methods

sizeOf# :: Mod m -> Int#

alignment# :: Mod m -> Int#

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

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

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

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

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

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

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

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

KnownNat m => Euclidean (Mod m)

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.

Defined in Data.Mod.Word

Methods

quotRem :: Mod m -> Mod m -> (Mod m, Mod m)

quot :: Mod m -> Mod m -> Mod m

rem :: Mod m -> Mod m -> Mod m

degree :: Mod m -> Natural

KnownNat m => Field (Mod m)

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.

Defined in Data.Mod.Word

KnownNat m => GcdDomain (Mod m)

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.

Defined in Data.Mod.Word

Methods

divide :: Mod m -> Mod m -> Maybe (Mod m)

gcd :: Mod m -> Mod m -> Mod m

lcm :: Mod m -> Mod m -> Mod m

coprime :: Mod m -> Mod m -> Bool

KnownNat m => Ring (Mod m)

Defined in Data.Mod.Word

Methods

negate :: Mod m -> Mod m

KnownNat m => Semiring (Mod m)

Defined in Data.Mod.Word

Methods

plus :: Mod m -> Mod m -> Mod m

zero :: Mod m

times :: Mod m -> Mod m -> Mod m

one :: Mod m

fromNatural :: Natural -> Mod m

Unbox (Mod m)

No validation checks are performed; reading untrusted data may corrupt internal invariants.

Defined in Data.Mod.Word

newtype MVector s (Mod m)

Defined in Data.Mod.Word

newtype MVector s (Mod m) = MV_Mod (MVector s Word)

type Rep (Mod m)

Defined in Data.Mod.Word

type Rep (Mod m) = D1 ('MetaData "Mod" "Data.Mod.Word" "mod-0.2.0.1-77HdehbY7w4DZp8RwhUH2U" 'True) (C1 ('MetaCons "Mod" 'PrefixI 'True) (S1 ('MetaSel ('Just "unMod") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 Word)))

newtype Vector (Mod m)

Defined in Data.Mod.Word

newtype Vector (Mod m) = V_Mod (Vector Word)

unMod :: Mod m -> Word

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

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

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

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

(^%) :: (KnownNat m, Integral a) => Mod m -> a -> Mod m infixr 8

Drop-in replacement for ^ with a bit 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