mod-0.1.2.2: Fast type-safe modular arithmetic
Copyright(c) 2017-2020 Andrew Lelechenko
LicenseMIT
MaintainerAndrew Lelechenko <andrew.lelechenko@gmail.com>
Safe HaskellNone
LanguageHaskell2010

Data.Mod

Description

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.

Synopsis

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 `modulo` 10)

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

Instances

Instances details
KnownNat m => Vector Vector (Mod m) Source # 
Instance details

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) Source # 
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 :: 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) Source # 
Instance details

Defined in Data.Mod

Methods

minBound :: Mod m #

maxBound :: Mod m #

KnownNat m => Enum (Mod m) Source # 
Instance details

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) Source # 
Instance details

Defined in Data.Mod

Methods

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

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

KnownNat m => Fractional (Mod m) Source #

See the warning about division above.

Instance details

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) Source # 
Instance details

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) Source # 
Instance details

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) Source # 
Instance details

Defined in Data.Mod

Methods

showsPrec :: Int -> Mod m -> ShowS #

show :: Mod m -> String #

showList :: [Mod m] -> ShowS #

Generic (Mod m) Source # 
Instance details

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) Source # 
Instance details

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) Source # 
Instance details

Defined in Data.Mod

Methods

rnf :: Mod m -> () #

KnownNat m => Prim (Mod m) Source # 
Instance details

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

See the warning about division above.

Instance details

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

See the warning about division above.

Instance details

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

See the warning about division above.

Instance details

Defined in Data.Mod

KnownNat m => Semiring (Mod m) Source # 
Instance details

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) Source # 
Instance details

Defined in Data.Mod

Methods

negate :: Mod m -> Mod m #

KnownNat m => Unbox (Mod m) Source # 
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 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.1.2.2-GzxqXYIw9J7ElcObj6IFg5" '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 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 `modulo` 10)

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

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