smart-math
Safe HaskellNone
LanguageHaskell2010

Numeric.Data.ModP

Description

Provides the ModP type for modular arithmetic.

Since: 0.1

Synopsis

Type

data ModP (p :: Nat) a where Source #

Newtype wrapper that represents \( \mathbb{Z}/p\mathbb{Z} \) for prime p. ModP is a Field i.e. supports addition, subtraction, multiplication, and division.

When constructing a ModP p a we must verify that p is prime and the type a is large enough to accommodate p, hence the possible failure.

Examples

Expand
>>> import Data.Text.Display (display)
>>> display $ unsafeModP @7 10
"3 (mod 7)"

Since: 0.1

Bundled Patterns

pattern MkModP :: a -> ModP p a

Unidirectional pattern synonym for ModP. This allows us to pattern match on a modp term without exposing the unsafe internal details.

Since: 0.1

Instances

Instances details
HasField "unModP" (ModP p a) a Source #

Since: 0.1

Instance details

Defined in Numeric.Data.ModP.Internal

Methods

getField :: ModP p a -> a #

(k ~ A_Getter, x ~ a, y ~ a) => LabelOptic "unModP" k (ModP p a) (ModP p a) x y Source #

Since: 0.1

Instance details

Defined in Numeric.Data.ModP.Internal

Methods

labelOptic :: Optic k NoIx (ModP p a) (ModP p a) x y Source #

Lift a => Lift (ModP p a :: Type) Source #

Since: 0.1

Instance details

Defined in Numeric.Data.ModP.Internal

Methods

lift :: Quote m => ModP p a -> m Exp #

liftTyped :: forall (m :: Type -> Type). Quote m => ModP p a -> Code m (ModP p a) #

Foldable (ModP p) Source #

Since: 0.1

Instance details

Defined in Numeric.Data.ModP.Internal

Methods

fold :: Monoid m => ModP p m -> m #

foldMap :: Monoid m => (a -> m) -> ModP p a -> m #

foldMap' :: Monoid m => (a -> m) -> ModP p a -> m #

foldr :: (a -> b -> b) -> b -> ModP p a -> b #

foldr' :: (a -> b -> b) -> b -> ModP p a -> b #

foldl :: (b -> a -> b) -> b -> ModP p a -> b #

foldl' :: (b -> a -> b) -> b -> ModP p a -> b #

foldr1 :: (a -> a -> a) -> ModP p a -> a #

foldl1 :: (a -> a -> a) -> ModP p a -> a #

toList :: ModP p a -> [a] #

null :: ModP p a -> Bool #

length :: ModP p a -> Int #

elem :: Eq a => a -> ModP p a -> Bool #

maximum :: Ord a => ModP p a -> a #

minimum :: Ord a => ModP p a -> a #

sum :: Num a => ModP p a -> a #

product :: Num a => ModP p a -> a #

(AMonoid a, FromInteger a, KnownNat p, MaybeUpperBounded a, MEuclidean a, ToInteger a, Typeable a) => AGroup (ModP p a) Source #

Since: 0.1

Instance details

Defined in Numeric.Data.ModP.Internal

Methods

(.-.) :: ModP p a -> ModP p a -> ModP p a Source #

(AMonoid a, FromInteger a, KnownNat p, MaybeUpperBounded a, MEuclidean a, ToInteger a, Typeable a) => AMonoid (ModP p a) Source #

WARNING: Partial

Since: 0.1

Instance details

Defined in Numeric.Data.ModP.Internal

Methods

zero :: ModP p a Source #

(ASemigroup a, FromInteger a, KnownNat p, MaybeUpperBounded a, MEuclidean a, ToInteger a) => ASemigroup (ModP p a) Source #

Since: 0.1

Instance details

Defined in Numeric.Data.ModP.Internal

Methods

(.+.) :: ModP p a -> ModP p a -> ModP p a Source #

(AMonoid a, FromInteger a, KnownNat p, MaybeUpperBounded a, MEuclidean a, ToInteger a, Typeable a) => Field (ModP p a) Source #

Since: 0.1

Instance details

Defined in Numeric.Data.ModP.Internal

(AMonoid a, FromInteger a, KnownNat p, MaybeUpperBounded a, MEuclidean a, ToInteger a, Typeable a) => MetricSpace (ModP p a) Source #

Since: 0.1

Instance details

Defined in Numeric.Data.ModP.Internal

Methods

diffR :: ModP p a -> ModP p a -> Double Source #

(FromInteger a, KnownNat p, MaybeUpperBounded a, MEuclidean a, ToInteger a, Typeable a) => MGroup (ModP p a) Source #

Since: 0.1

Instance details

Defined in Numeric.Data.ModP.Internal

Methods

(.%.) :: ModP p a -> ModP p a -> ModP p a Source #

(FromInteger a, KnownNat p, MaybeUpperBounded a, MEuclidean a, ToInteger a, Typeable a) => MMonoid (ModP p a) Source #

WARNING: Partial

Since: 0.1

Instance details

Defined in Numeric.Data.ModP.Internal

Methods

one :: ModP p a Source #

(FromInteger a, KnownNat p, MaybeUpperBounded a, MEuclidean a, ToInteger a) => MSemigroup (ModP p a) Source #

Since: 0.1

Instance details

Defined in Numeric.Data.ModP.Internal

Methods

(.*.) :: ModP p a -> ModP p a -> ModP p a Source #

(AMonoid a, FromInteger a, KnownNat p, MaybeUpperBounded a, MEuclidean a, ToInteger a, Typeable a) => Ring (ModP p a) Source #

Since: 0.1

Instance details

Defined in Numeric.Data.ModP.Internal

(AMonoid a, FromInteger a, KnownNat p, MaybeUpperBounded a, MEuclidean a, ToInteger a, Typeable a) => Semifield (ModP p a) Source #

Since: 0.1

Instance details

Defined in Numeric.Data.ModP.Internal

(AMonoid a, FromInteger a, KnownNat p, MaybeUpperBounded a, MEuclidean a, ToInteger a, Typeable a) => Semiring (ModP p a) Source #

Since: 0.1

Instance details

Defined in Numeric.Data.ModP.Internal

(FromInteger a, KnownNat p, MaybeUpperBounded a, MEuclidean a, ToInteger a, Typeable a) => FromInteger (ModP p a) Source #

WARNING: Partial

Since: 0.1

Instance details

Defined in Numeric.Data.ModP.Internal

Methods

fromZ :: Integer -> ModP p a Source #

ToInteger a => ToInteger (ModP p a) Source #

Since: 0.1

Instance details

Defined in Numeric.Data.ModP.Internal

Methods

toZ :: ModP p a -> Integer Source #

ToRational a => ToRational (ModP p a) Source #

Since: 0.1

Instance details

Defined in Numeric.Data.ModP.Internal

Methods

toQ :: ModP p a -> Rational Source #

ToReal a => ToReal (ModP p a) Source #

Since: 0.1

Instance details

Defined in Numeric.Data.ModP.Internal

Methods

toR :: ModP p a -> Double Source #

(AMonoid a, FromInteger a, KnownNat p, MaybeUpperBounded a, MEuclidean a, ToInteger a, Typeable a) => LowerBounded (ModP p a) Source #

Since: 0.1

Instance details

Defined in Numeric.Data.ModP.Internal

Methods

lowerBound :: ModP p a Source #

(AMonoid a, FromInteger a, KnownNat p, MaybeUpperBounded a, MEuclidean a, ToInteger a, Typeable a) => MaybeLowerBounded (ModP p a) Source #

Since: 0.1

Instance details

Defined in Numeric.Data.ModP.Internal

Methods

maybeLowerBound :: Maybe (ModP p a) Source #

(FromInteger a, KnownNat p, MaybeUpperBounded a, MEuclidean a, ToInteger a, Typeable a) => MaybeUpperBounded (ModP p a) Source #

Since: 0.1

Instance details

Defined in Numeric.Data.ModP.Internal

Methods

maybeUpperBound :: Maybe (ModP p a) Source #

(FromInteger a, KnownNat p, MaybeUpperBounded a, MEuclidean a, ToInteger a, Typeable a) => UpperBounded (ModP p a) Source #

Since: 0.1

Instance details

Defined in Numeric.Data.ModP.Internal

Methods

upperBound :: ModP p a Source #

NFData a => NFData (ModP p a) Source #

Since: 0.1.0.0

Instance details

Defined in Numeric.Data.ModP.Internal

Methods

rnf :: ModP p a -> () #

(AMonoid a, FromInteger a, KnownNat p, MaybeUpperBounded a, MEuclidean a, ToInteger a, Typeable a) => Bounded (ModP p a) Source #

WARNING: Partial

Since: 0.1

Instance details

Defined in Numeric.Data.ModP.Internal

Methods

minBound :: ModP p a #

maxBound :: ModP p a #

Generic (ModP p a) Source # 
Instance details

Defined in Numeric.Data.ModP.Internal

Associated Types

type Rep (ModP p a)

Since: smart-math-0.1

Instance details

Defined in Numeric.Data.ModP.Internal

type Rep (ModP p a) = D1 ('MetaData "ModP" "Numeric.Data.ModP.Internal" "smart-math-0.1-inplace" 'True) (C1 ('MetaCons "UnsafeModP" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 a)))

Methods

from :: ModP p a -> Rep (ModP p a) x #

to :: Rep (ModP p a) x -> ModP p a #

(KnownNat p, Show a) => Show (ModP p a) Source #

Since: 0.1

Instance details

Defined in Numeric.Data.ModP.Internal

Methods

showsPrec :: Int -> ModP p a -> ShowS #

show :: ModP p a -> String #

showList :: [ModP p a] -> ShowS #

Eq a => Eq (ModP p a) Source #

Since: 0.1

Instance details

Defined in Numeric.Data.ModP.Internal

Methods

(==) :: ModP p a -> ModP p a -> Bool #

(/=) :: ModP p a -> ModP p a -> Bool #

Ord a => Ord (ModP p a) Source #

Since: 0.1

Instance details

Defined in Numeric.Data.ModP.Internal

Methods

compare :: ModP p a -> ModP p a -> Ordering #

(<) :: ModP p a -> ModP p a -> Bool #

(<=) :: ModP p a -> ModP p a -> Bool #

(>) :: ModP p a -> ModP p a -> Bool #

(>=) :: ModP p a -> ModP p a -> Bool #

max :: ModP p a -> ModP p a -> ModP p a #

min :: ModP p a -> ModP p a -> ModP p a #

Hashable a => Hashable (ModP p a) Source #

Since: 0.1.0.0

Instance details

Defined in Numeric.Data.ModP.Internal

Methods

hashWithSalt :: Int -> ModP p a -> Int Source #

hash :: ModP p a -> Int Source #

(KnownNat p, Show a) => Display (ModP p a) Source #

Since: 0.1

Instance details

Defined in Numeric.Data.ModP.Internal

Methods

displayBuilder :: ModP p a -> Builder Source #

displayList :: [ModP p a] -> Builder Source #

displayPrec :: Int -> ModP p a -> Builder Source #

type Rep (ModP p a) Source #

Since: 0.1

Instance details

Defined in Numeric.Data.ModP.Internal

type Rep (ModP p a) = D1 ('MetaData "ModP" "Numeric.Data.ModP.Internal" "smart-math-0.1-inplace" 'True) (C1 ('MetaCons "UnsafeModP" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 a)))

Creation

mkModP :: forall (p :: Nat) a. (FromInteger a, KnownNat p, MaybeUpperBounded a, MEuclidean a, ToInteger a, Typeable a) => a -> Either String (ModP p a) Source #

Constructor for ModP. Fails if p is not prime. This uses the Miller-Rabin primality test, which has complexity \(O(k \log^3 p)\), and we take \(k = 100\). See wikipedia for more details.

Examples

Expand
>>> mkModP @5 7
Right (MkModP 2 (mod 5))

>>> mkModP @10 7
Left "Received non-prime: 10"

>>> mkModP @128 (9 :: Int8)
Left "Type 'Int8' has a maximum size of 127. This is not large enough to safely implement mod 128."

Since: 0.1

mkModPTH :: forall (p :: Nat) a. (FromInteger a, KnownNat p, Lift a, MaybeUpperBounded a, MEuclidean a, ToInteger a, Typeable a) => a -> Code Q (ModP p a) Source #

Template haskell for creating a ModP at compile-time.

Examples

Expand
>>> $$(mkModPTH @11 7)
MkModP 7 (mod 11)

Since: 0.1

unsafeModP :: forall (p :: Nat) a. (FromInteger a, HasCallStack, KnownNat p, MaybeUpperBounded a, MEuclidean a, ToInteger a, Typeable a) => a -> ModP p a Source #

Variant of mkModP that throws an error when given a non-prime.

WARNING: Partial

Examples

Expand
>>> unsafeModP @7 12
MkModP 5 (mod 7)

Since: 0.1

reallyUnsafeModP :: forall (p :: Nat) a. (FromInteger a, KnownNat p, MEuclidean a) => a -> ModP p a Source #

This function reduces the argument modulo p but does not check that p is prime. Note that the correct behavior of some functionality (e.g. division) is reliant on primality, so this is dangerous. This is intended only for when we absolutely know p is prime and the check is undesirable for performance reasons. Exercise extreme caution.

Since: 0.1

Elimination

unModP :: forall (p :: Nat) a. ModP p a -> a Source #

Since: 0.1

Functions

invert :: forall (p :: Nat) a. (FromInteger a, KnownNat p, MEuclidean a, ToInteger a) => ModP p a -> ModP p a Source #

Given non-zero \(d\), returns the inverse i.e. finds \(e\) s.t.

\[ de \equiv 1 \pmod p. \]

Examples

Expand

findInverse >>> invert $ unsafeModP @7 5 MkModP 3 (mod 7)

>>> invert $ unsafeModP @19 12
MkModP 8 (mod 19)

Since: 0.1

Optics

We provide a ReversedPrism' _MkModP that allows for total elimination and partial construction, along with a LabelOptic Getter for #unModP.

Examples

Expand
>>> :set -XOverloadedLabels
>>> import Optics.Core (view)
>>> let n = $$(mkModPTH @7 9)
>>> view #unModP n
2

_MkModP :: forall (p :: Nat) a. (FromInteger a, KnownNat p, MaybeUpperBounded a, MEuclidean a, ToInteger a, Typeable a) => ReversedPrism' (ModP p a) a Source #

ReversedPrism' that enables total elimination and partial construction.

Examples

Expand
>>> import Optics.Core (view)
>>> n = $$(mkModPTH @7 9)
>>> view _MkModP n
2

>>> rmatching (_MkModP @7) 9
Right (MkModP 2 (mod 7))

>>> rmatching (_MkModP @6) 9
Left 9

Since: 0.1

rmatching :: (Is (ReversedOptic k) An_AffineTraversal, ReversibleOptic k) => Optic k NoIx b a t s -> s -> Either t a Source #

Reversed matching. Useful with smart-constructor optics.

Since: 0.1