Data.Mod

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

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

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

KnownNat m => Vector Vector (Mod m)

Defined in Data.Mod

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

KnownNat m => MVector MVector (Mod m)

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

Methods

minBound :: Mod m

maxBound :: Mod m

KnownNat m => Enum (Mod m)

Defined in Data.Mod

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

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

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

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

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

Methods

showsPrec :: Int -> Mod m -> ShowS

show :: Mod m -> String

showList :: [Mod m] -> ShowS

Generic (Mod m)

Defined in Data.Mod

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

Defined in Data.Mod

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

Methods

rnf :: Mod m -> ()

KnownNat m => Prim (Mod m)

Defined in Data.Mod

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

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

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

KnownNat m => Semiring (Mod m)

Defined in Data.Mod

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

Methods

negate :: Mod m -> Mod m

KnownNat m => Unbox (Mod m)

Defined in Data.Mod

newtype MVector s (Mod m)

Unboxed vectors of Mod cause more nursery allocations than boxed ones, but reduce pressure on garbage collector, especially for large vectors.

Defined in Data.Mod

newtype MVector s (Mod m) = ModMVec (MVector s (Mod m))

type Rep (Mod m)

Defined in Data.Mod

type Rep (Mod m) = D1 (MetaData "Mod" "Data.Mod" "mod-0.1.2.0-LHa6CakLkKh9OqsXjiPgMx" True) (C1 (MetaCons "Mod" PrefixI True) (S1 (MetaSel (Just "unMod") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 Natural)))

newtype Vector (Mod m)

Unboxed vectors of Mod cause more nursery allocations than boxed ones, but reduce pressure on garbage collector, especially for large vectors.

Defined in Data.Mod

newtype Vector (Mod m) = ModVec (Vector (Mod m))

unMod :: Mod m -> Natural

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