Copyright	(c) 2017-2020 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 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 :: KnownNat m => Mod m -> Maybe (Mod m)
(^%) :: (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 `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