arithmoi-0.13.0.0: Efficient basic number-theoretic functions.

Copyright | (c) 2019 Andrew Lelechenko
License | MIT
Maintainer | Andrew Lelechenko <andrew.lelechenko@gmail.com>
Safe Haskell | Safe-Inferred
Language | Haskell2010

Math.NumberTheory.Moduli.Singleton

Contents

- SFactors singleton
- CyclicGroup singleton
- SFactors <=> CyclicGroup
- Some wrapper

Description

Singleton data types.

Synopsis

- data SFactors a (m :: Nat)
- sfactors :: forall a m. (Ord a, UniqueFactorisation a, KnownNat m) => SFactors a m
- someSFactors :: (Ord a, Num a) => [(Prime a, Word)] -> Some (SFactors a)
- unSFactors :: SFactors a m -> [(Prime a, Word)]
- proofFromSFactors :: Integral a => SFactors a m -> () :- KnownNat m
- data CyclicGroup a (m :: Nat)
- cyclicGroup :: forall a m. (Integral a, UniqueFactorisation a, KnownNat m) => Maybe (CyclicGroup a m)
- cyclicGroupFromFactors :: (Eq a, Num a) => [(Prime a, Word)] -> Maybe (Some (CyclicGroup a))
- cyclicGroupFromModulo :: (Integral a, UniqueFactorisation a) => a -> Maybe (Some (CyclicGroup a))
- proofFromCyclicGroup :: Integral a => CyclicGroup a m -> () :- KnownNat m
- pattern CG2 :: CyclicGroup a m
- pattern CG4 :: CyclicGroup a m
- pattern CGOddPrimePower :: Prime a -> Word -> CyclicGroup a m
- pattern CGDoubleOddPrimePower :: Prime a -> Word -> CyclicGroup a m
- cyclicGroupToSFactors :: Num a => CyclicGroup a m -> SFactors a m
- sfactorsToCyclicGroup :: (Eq a, Num a) => SFactors a m -> Maybe (CyclicGroup a m)
- data Some (a :: Nat -> Type) where
  - Some :: a m -> Some a

# SFactors singleton

data SFactors a (m :: Nat) Source #

This singleton data type establishes a correspondence between a modulo `m` on type level and its factorisation on term level.

#### Instances

Instances details

Show a => Show (Some (SFactors a)) Source # |
Instance details Defined in Math.NumberTheory.Moduli.Singleton Methods showsPrec :: Int -> Some (SFactors a) -> ShowS Source # show :: Some (SFactors a) -> String Source # showList :: [Some (SFactors a)] -> ShowS Source #
NFData a => NFData (Some (SFactors a)) Source # |
Instance details Defined in Math.NumberTheory.Moduli.Singleton Methods rnf :: Some (SFactors a) -> () Source #
Ord a => Eq (Some (SFactors a)) Source # |
Instance details Defined in Math.NumberTheory.Moduli.Singleton Methods (==) :: Some (SFactors a) -> Some (SFactors a) -> Bool Source # (/=) :: Some (SFactors a) -> Some (SFactors a) -> Bool Source #
Ord a => Ord (Some (SFactors a)) Source # |

Instance details

Defined in Math.NumberTheory.Moduli.Singleton

Methods

compare :: Some (SFactors a) -> Some (SFactors a) -> Ordering Source #

(<) :: Some (SFactors a) -> Some (SFactors a) -> Bool Source #

(<=) :: Some (SFactors a) -> Some (SFactors a) -> Bool Source #

(>) :: Some (SFactors a) -> Some (SFactors a) -> Bool Source #

(>=) :: Some (SFactors a) -> Some (SFactors a) -> Bool Source #

max :: Some (SFactors a) -> Some (SFactors a) -> Some (SFactors a) Source #

min :: Some (SFactors a) -> Some (SFactors a) -> Some (SFactors a) Source #

Generic (SFactors a m) Source # |
Instance details Defined in Math.NumberTheory.Moduli.Singleton Associated Types type Rep (SFactors a m) :: Type -> Type Source # Methods from :: SFactors a m -> Rep (SFactors a m) x Source # to :: Rep (SFactors a m) x -> SFactors a m Source #
Show a => Show (SFactors a m) Source # |
Instance details Defined in Math.NumberTheory.Moduli.Singleton Methods showsPrec :: Int -> SFactors a m -> ShowS Source # show :: SFactors a m -> String Source # showList :: [SFactors a m] -> ShowS Source #
NFData a => NFData (SFactors a m) Source # |
Instance details Defined in Math.NumberTheory.Moduli.Singleton Methods rnf :: SFactors a m -> () Source #
Eq (SFactors a m) Source # |
Instance details Defined in Math.NumberTheory.Moduli.Singleton Methods (==) :: SFactors a m -> SFactors a m -> Bool Source # (/=) :: SFactors a m -> SFactors a m -> Bool Source #
Ord (SFactors a m) Source # |

Instance details

Defined in Math.NumberTheory.Moduli.Singleton

Methods

compare :: SFactors a m -> SFactors a m -> Ordering Source #

(<) :: SFactors a m -> SFactors a m -> Bool Source #

(<=) :: SFactors a m -> SFactors a m -> Bool Source #

(>) :: SFactors a m -> SFactors a m -> Bool Source #

(>=) :: SFactors a m -> SFactors a m -> Bool Source #

max :: SFactors a m -> SFactors a m -> SFactors a m Source #

min :: SFactors a m -> SFactors a m -> SFactors a m Source #

type Rep (SFactors a m) Source # |
Instance details Defined in Math.NumberTheory.Moduli.Singleton type Rep (SFactors a m) = D1 ('MetaData "SFactors" "Math.NumberTheory.Moduli.Singleton" "arithmoi-0.13.0.0-Gu7wAZ5ppC1YpMjsEnZVk" 'True) (C1 ('MetaCons "SFactors" 'PrefixI 'True) (S1 ('MetaSel ('Just "unSFactors") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 [(Prime a, Word)])))

sfactors :: forall a m. (Ord a, UniqueFactorisation a, KnownNat m) => SFactors a m Source #

Create a singleton from a type-level positive modulo `m`, passed in a constraint.

    >>> :set -XDataKinds
    >>> sfactors :: SFactors Integer 13
    SFactors {unSFactors = [(Prime 13,1)]}

someSFactors :: (Ord a, Num a) => [(Prime a, Word)] -> Some (SFactors a) Source #

Create a singleton from factors of `m`. Factors must be distinct, as in output of `factorise`.

    >>> import Math.NumberTheory.Primes
    >>> someSFactors (factorise 98)
    SFactors {unSFactors = [(Prime 2,1),(Prime 7,2)]}

unSFactors :: SFactors a m -> [(Prime a, Word)] Source #

Factors of `m`.

proofFromSFactors :: Integral a => SFactors a m -> () :- KnownNat m Source #

Convert a singleton to a proof that `m` is known. Usage example:

    toModulo :: SFactors Integer m -> Natural
    toModulo t = case proofFromSFactors t of Sub Dict -> natVal t

# CyclicGroup singleton

data CyclicGroup a (m :: Nat) Source #

This singleton data type establishes a correspondence between a modulo `m` on type level and a cyclic group of the same order on term level.

#### Instances

Instances details

Show a => Show (Some (CyclicGroup a)) Source # |
Instance details Defined in Math.NumberTheory.Moduli.Singleton Methods showsPrec :: Int -> Some (CyclicGroup a) -> ShowS Source # show :: Some (CyclicGroup a) -> String Source # showList :: [Some (CyclicGroup a)] -> ShowS Source #
NFData a => NFData (Some (CyclicGroup a)) Source # |
Instance details Defined in Math.NumberTheory.Moduli.Singleton Methods rnf :: Some (CyclicGroup a) -> () Source #
Eq a => Eq (Some (CyclicGroup a)) Source # |
Instance details Defined in Math.NumberTheory.Moduli.Singleton Methods (==) :: Some (CyclicGroup a) -> Some (CyclicGroup a) -> Bool Source # (/=) :: Some (CyclicGroup a) -> Some (CyclicGroup a) -> Bool Source #
Ord a => Ord (Some (CyclicGroup a)) Source # |

Instance details

Defined in Math.NumberTheory.Moduli.Singleton

Methods

compare :: Some (CyclicGroup a) -> Some (CyclicGroup a) -> Ordering Source #

(<) :: Some (CyclicGroup a) -> Some (CyclicGroup a) -> Bool Source #

(<=) :: Some (CyclicGroup a) -> Some (CyclicGroup a) -> Bool Source #

(>) :: Some (CyclicGroup a) -> Some (CyclicGroup a) -> Bool Source #

(>=) :: Some (CyclicGroup a) -> Some (CyclicGroup a) -> Bool Source #

max :: Some (CyclicGroup a) -> Some (CyclicGroup a) -> Some (CyclicGroup a) Source #

min :: Some (CyclicGroup a) -> Some (CyclicGroup a) -> Some (CyclicGroup a) Source #

Generic (CyclicGroup a m) Source # |
Instance details Defined in Math.NumberTheory.Moduli.Singleton Associated Types type Rep (CyclicGroup a m) :: Type -> Type Source # Methods from :: CyclicGroup a m -> Rep (CyclicGroup a m) x Source # to :: Rep (CyclicGroup a m) x -> CyclicGroup a m Source #
Show a => Show (CyclicGroup a m) Source # |
Instance details Defined in Math.NumberTheory.Moduli.Singleton Methods showsPrec :: Int -> CyclicGroup a m -> ShowS Source # show :: CyclicGroup a m -> String Source # showList :: [CyclicGroup a m] -> ShowS Source #
NFData a => NFData (CyclicGroup a m) Source # |
Instance details Defined in Math.NumberTheory.Moduli.Singleton Methods rnf :: CyclicGroup a m -> () Source #
Eq (CyclicGroup a m) Source # |
Instance details Defined in Math.NumberTheory.Moduli.Singleton Methods (==) :: CyclicGroup a m -> CyclicGroup a m -> Bool Source # (/=) :: CyclicGroup a m -> CyclicGroup a m -> Bool Source #
Ord (CyclicGroup a m) Source # |

Instance details

Defined in Math.NumberTheory.Moduli.Singleton

Methods

compare :: CyclicGroup a m -> CyclicGroup a m -> Ordering Source #

(<) :: CyclicGroup a m -> CyclicGroup a m -> Bool Source #

(<=) :: CyclicGroup a m -> CyclicGroup a m -> Bool Source #

(>) :: CyclicGroup a m -> CyclicGroup a m -> Bool Source #

(>=) :: CyclicGroup a m -> CyclicGroup a m -> Bool Source #

max :: CyclicGroup a m -> CyclicGroup a m -> CyclicGroup a m Source #

min :: CyclicGroup a m -> CyclicGroup a m -> CyclicGroup a m Source #

type Rep (CyclicGroup a m) Source # |

Instance details

Defined in Math.NumberTheory.Moduli.Singleton

type Rep (CyclicGroup a m) = D1 ('MetaData "CyclicGroup" "Math.NumberTheory.Moduli.Singleton" "arithmoi-0.13.0.0-Gu7wAZ5ppC1YpMjsEnZVk" 'False) ((C1 ('MetaCons "CG2'" 'PrefixI 'False) (U1 :: Type -> Type) :+: C1 ('MetaCons "CG4'" 'PrefixI 'False) (U1 :: Type -> Type)) :+: (C1 ('MetaCons "CGOddPrimePower'" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (Prime a)) :*: S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 Word)) :+: C1 ('MetaCons "CGDoubleOddPrimePower'" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (Prime a)) :*: S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 Word))))

cyclicGroup :: forall a m. (Integral a, UniqueFactorisation a, KnownNat m) => Maybe (CyclicGroup a m) Source #

Create a singleton from a type-level positive modulo `m`, passed in a constraint.

    >>> :set -XDataKinds
    >>> import Data.Maybe
    >>> cyclicGroup :: Maybe (CyclicGroup Integer 169)
    Just (CGOddPrimePower' (Prime 13) 2)

    >>> :set -XTypeOperators -XNoStarIsType
    >>> import GHC.TypeNats
    >>> sfactorsToCyclicGroup (sfactors :: SFactors Integer 4)
    Just CG4'
    >>> sfactorsToCyclicGroup (sfactors :: SFactors Integer (2 * 13 ^ 3))
    Just (CGDoubleOddPrimePower' (Prime 13) 3)
    >>> sfactorsToCyclicGroup (sfactors :: SFactors Integer  (4 * 13))
    Nothing

cyclicGroupFromFactors :: (Eq a, Num a) => [(Prime a, Word)] -> Maybe (Some (CyclicGroup a)) Source #

Create a singleton from factors. Factors must be distinct, as in output of `factorise`.

cyclicGroupFromModulo :: (Integral a, UniqueFactorisation a) => a -> Maybe (Some (CyclicGroup a)) Source #

Similar to `cyclicGroupFromFactors` . `factorise`, but much faster, because it but performes only one primality test instead of full factorisation.

proofFromCyclicGroup :: Integral a => CyclicGroup a m -> () :- KnownNat m Source #

Convert a cyclic group to a proof that `m` is known. Usage example:

    toModulo :: CyclicGroup Integer m -> Natural
    toModulo t = case proofFromCyclicGroup t of Sub Dict -> natVal t

pattern CG2 :: CyclicGroup a m Source #

Unidirectional pattern for residues modulo 2.

pattern CG4 :: CyclicGroup a m Source #

Unidirectional pattern for residues modulo 4.

pattern CGOddPrimePower :: Prime a -> Word -> CyclicGroup a m Source #

Unidirectional pattern for residues modulo `p`^`k` for odd prime `p`.

pattern CGDoubleOddPrimePower :: Prime a -> Word -> CyclicGroup a m Source #

Unidirectional pattern for residues modulo 2`p`^`k` for odd prime `p`.

# SFactors <=> CyclicGroup

cyclicGroupToSFactors :: Num a => CyclicGroup a m -> SFactors a m Source #

Invert `sfactorsToCyclicGroup`.

    >>> import Data.Maybe
    >>> cyclicGroupToSFactors (fromJust (sfactorsToCyclicGroup (sfactors :: SFactors Integer 4)))
    SFactors {unSFactors = [(Prime 2,2)]}

sfactorsToCyclicGroup :: (Eq a, Num a) => SFactors a m -> Maybe (CyclicGroup a m) Source #

Check whether a multiplicative group of residues, characterized by its modulo, is cyclic and, if yes, return its form.

    >>> :set -XTypeOperators -XNoStarIsType
    >>> import GHC.TypeNats
    >>> sfactorsToCyclicGroup (sfactors :: SFactors Integer 4)
    Just CG4'
    >>> sfactorsToCyclicGroup (sfactors :: SFactors Integer (2 * 13 ^ 3))
    Just (CGDoubleOddPrimePower' (Prime 13) 3)
    >>> sfactorsToCyclicGroup (sfactors :: SFactors Integer  (4 * 13))
    Nothing

# Some wrapper

data Some (a :: Nat -> Type) where Source #

Wrapper to hide an unknown type-level natural.

Constructors

Some :: a m -> Some a |

#### Instances

Instances details

Show a => Show (Some (CyclicGroup a)) Source # |
Instance details Defined in Math.NumberTheory.Moduli.Singleton Methods showsPrec :: Int -> Some (CyclicGroup a) -> ShowS Source # show :: Some (CyclicGroup a) -> String Source # showList :: [Some (CyclicGroup a)] -> ShowS Source #
Show a => Show (Some (SFactors a)) Source # |
Instance details Defined in Math.NumberTheory.Moduli.Singleton Methods showsPrec :: Int -> Some (SFactors a) -> ShowS Source # show :: Some (SFactors a) -> String Source # showList :: [Some (SFactors a)] -> ShowS Source #
NFData a => NFData (Some (CyclicGroup a)) Source # |
Instance details Defined in Math.NumberTheory.Moduli.Singleton Methods rnf :: Some (CyclicGroup a) -> () Source #
NFData a => NFData (Some (SFactors a)) Source # |
Instance details Defined in Math.NumberTheory.Moduli.Singleton Methods rnf :: Some (SFactors a) -> () Source #
Eq a => Eq (Some (CyclicGroup a)) Source # |
Instance details Defined in Math.NumberTheory.Moduli.Singleton Methods (==) :: Some (CyclicGroup a) -> Some (CyclicGroup a) -> Bool Source # (/=) :: Some (CyclicGroup a) -> Some (CyclicGroup a) -> Bool Source #
Ord a => Eq (Some (SFactors a)) Source # |
Instance details Defined in Math.NumberTheory.Moduli.Singleton Methods (==) :: Some (SFactors a) -> Some (SFactors a) -> Bool Source # (/=) :: Some (SFactors a) -> Some (SFactors a) -> Bool Source #
Ord a => Ord (Some (CyclicGroup a)) Source # |

Instance details

Defined in Math.NumberTheory.Moduli.Singleton

Methods

compare :: Some (CyclicGroup a) -> Some (CyclicGroup a) -> Ordering Source #

(<) :: Some (CyclicGroup a) -> Some (CyclicGroup a) -> Bool Source #

(<=) :: Some (CyclicGroup a) -> Some (CyclicGroup a) -> Bool Source #

(>) :: Some (CyclicGroup a) -> Some (CyclicGroup a) -> Bool Source #

(>=) :: Some (CyclicGroup a) -> Some (CyclicGroup a) -> Bool Source #

max :: Some (CyclicGroup a) -> Some (CyclicGroup a) -> Some (CyclicGroup a) Source #

min :: Some (CyclicGroup a) -> Some (CyclicGroup a) -> Some (CyclicGroup a) Source #

Ord a => Ord (Some (SFactors a)) Source # |

Instance details

Defined in Math.NumberTheory.Moduli.Singleton

Methods

compare :: Some (SFactors a) -> Some (SFactors a) -> Ordering Source #

(<) :: Some (SFactors a) -> Some (SFactors a) -> Bool Source #

(<=) :: Some (SFactors a) -> Some (SFactors a) -> Bool Source #

(>) :: Some (SFactors a) -> Some (SFactors a) -> Bool Source #

(>=) :: Some (SFactors a) -> Some (SFactors a) -> Bool Source #

max :: Some (SFactors a) -> Some (SFactors a) -> Some (SFactors a) Source #

min :: Some (SFactors a) -> Some (SFactors a) -> Some (SFactors a) Source #