Data.Mod

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

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 modulo 10: …−17, −7, 3, 13, 23…

>>> :set -XDataKinds
>>> 3 + 8 :: Mod 10
(1 `modulo` 10) -- because 3 + 8 = 11 ≡ 1 (mod 10)

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

Instances

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

NFData (Mod m)

Defined in Data.Mod

Methods

rnf :: Mod m -> ()

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

type Rep (Mod m)

Defined in Data.Mod

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

unMod :: Mod m -> Natural

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

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
Just (7 `modulo` 10) -- because 3 * 7 = 21 ≡ 1 (mod 10)
>>> invertMod 4 :: Mod 10
Nothing -- because 4 and 10 are not coprime

(^%) :: (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
(1 `modulo` 10) -- because 3 ^ 4 = 81 ≡ 1 (mod 10)
>>> 3 ^% (-1) :: Mod 10
(7 `modulo` 10) -- because 3 * 7 = 21 ≡ 1 (mod 10)
>>> 4 ^% (-1) :: Mod 10
(*** Exception: divide by zero -- because 4 and 10 are not coprime