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

NFData (Mod m)

Defined in Data.Mod.Word

Methods

rnf :: Mod m -> ()

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

type Rep (Mod m)

Defined in Data.Mod.Word

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

unMod :: Mod m -> Word

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