Module

Data.ModularArithmetic

Package: purescript-modular-arithmetic
Repository: hdgarrood/purescript-modular-arithmetic

#Z Source

newtype Z m

Integers modulo some positive integer m.

The type argument should be a positive integer of the kind defined by purescript-typelevel. This way, the modulus that you're working with is specified in the type. Note that even though the modulus is captured at the type level, you can still use modulus values which are not known at compile time, with the reifyIntP function.

This type forms a commutative ring for any positive integer m, and additionally a field when m is prime. Unlike Int and Number, though, all of these instances are fully law-abiding.

The runtime representation is identical to that of Int, except that values are guaranteed to be between 0 and m-1.

Instances

Eq (Z m)
Ord (Z m)
Show (Z m)
(Pos m) => Bounded (Z m)
(Pos m) => Enum (Z m)
(Pos m) => BoundedEnum (Z m)
(Pos m) => Semiring (Z m)
(Pos m) => Ring (Z m)
(Pos m) => CommutativeRing (Z m)
(Prime m) => DivisionRing (Z m)
(Prime m) => EuclideanRing (Z m)
(Prime m) => Field (Z m)
(Pos m) => Arbitrary (Z m)

#mkZ Source

mkZ :: forall m. Pos m => Int -> Z m

Smart constructor for Z values.

#runZ Source

runZ :: forall m. Z m -> Int

Get at the underlying Int.

#modulus Source

modulus :: forall m. Pos m => Z m -> Int

Convenience function for accessing m at the value level.

#inverse Source

inverse :: forall m. Pos m => Z m -> Maybe (Z m)

Compute a multiplicative inverse of some nonzero number in Z_m. Note that an inverse exists if and only if the input and m are coprime. If this is not the case, this function returns Nothing.

#enumerate Source

enumerate :: forall m. Pos m => NonEmpty Array (Z m)

List all members of Z_m.

#Prime Source

class (Pos m) <= Prime m

This class specifies that a type-level integer is prime; that is, it has exactly 2 divisors: itself, and 1.

Sadly, only a small number of primes have instances right now. Hopefully this will change in the future.

Instances

Modules: Data.ModularArithmetic