Data.Mod.Word

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

This module supports only moduli, which fit into Word. Use (slower) Data.Mod to handle 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 `modulo` 10)

Warning: division by residue, which is not coprime with the modulo, throws DivideByZero. Consider using invertMod for non-prime moduli.

Instances

Vector Vector (Mod m)

Defined in Data.Mod.Word

Methods

basicUnsafeFreeze :: PrimMonad m0 => Mutable Vector (PrimState m0) (Mod m) -> m0 (Vector (Mod m))

basicUnsafeThaw :: PrimMonad m0 => Vector (Mod m) -> m0 (Mutable Vector (PrimState m0) (Mod m))

basicLength :: Vector (Mod m) -> Int

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

basicUnsafeIndexM :: Monad m0 => Vector (Mod m) -> Int -> m0 (Mod m)

basicUnsafeCopy :: PrimMonad m0 => Mutable Vector (PrimState m0) (Mod m) -> Vector (Mod m) -> m0 ()

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

MVector MVector (Mod m)

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 :: PrimMonad m0 => Int -> m0 (MVector (PrimState m0) (Mod m))

basicInitialize :: PrimMonad m0 => MVector (PrimState m0) (Mod m) -> m0 ()

basicUnsafeReplicate :: PrimMonad m0 => Int -> Mod m -> m0 (MVector (PrimState m0) (Mod m))

basicUnsafeRead :: PrimMonad m0 => MVector (PrimState m0) (Mod m) -> Int -> m0 (Mod m)

basicUnsafeWrite :: PrimMonad m0 => MVector (PrimState m0) (Mod m) -> Int -> Mod m -> m0 ()

basicClear :: PrimMonad m0 => MVector (PrimState m0) (Mod m) -> m0 ()

basicSet :: PrimMonad m0 => MVector (PrimState m0) (Mod m) -> Mod m -> m0 ()

basicUnsafeCopy :: PrimMonad m0 => MVector (PrimState m0) (Mod m) -> MVector (PrimState m0) (Mod m) -> m0 ()

basicUnsafeMove :: PrimMonad m0 => MVector (PrimState m0) (Mod m) -> MVector (PrimState m0) (Mod m) -> m0 ()

basicUnsafeGrow :: PrimMonad m0 => MVector (PrimState m0) (Mod m) -> Int -> m0 (MVector (PrimState m0) (Mod m))

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]

Eq (Mod m)

Defined in Data.Mod.Word

Methods

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

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

KnownNat m => Fractional (Mod m)

See the warning about division above.

Defined in Data.Mod.Word

Methods

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

recip :: Mod m -> Mod m

fromRational :: Rational -> 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

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

KnownNat m => Show (Mod m)

Defined in Data.Mod.Word

Methods

showsPrec :: Int -> Mod m -> ShowS

show :: Mod m -> String

showList :: [Mod m] -> ShowS

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

Storable (Mod m)

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

NFData (Mod m)

Defined in Data.Mod.Word

Methods

rnf :: Mod m -> ()

Prim (Mod m)

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 => GcdDomain (Mod m)

See the warning about division above.

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 => Euclidean (Mod m)

See the warning about division above.

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)

See the warning about division above.

Defined in Data.Mod.Word

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

KnownNat m => Ring (Mod m)

Defined in Data.Mod.Word

Methods

negate :: Mod m -> Mod m

Unbox (Mod m)

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.1.2.2-GzxqXYIw9J7ElcObj6IFg5" '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 `modulo` 10)

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

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

>>> :set -XDataKinds
>>> invertMod 3 :: Mod 10 -- 3 * 7 = 21 ≡ 1 (mod 10)
Just (7 `modulo` 10)
>>> 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 modulo.

Building with -O triggers a rewrite rule ^ = ^%.

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