Safe Haskell | None |
---|---|
Language | Haskell2010 |
This file defines types and operations for type-level representation and manipulation of factored integers. It relies on TH, so the documentation will be difficult to read. See comments for better documentation.
- newtype Factored = F [PrimePower]
- type SFactored = (Sing :: Factored -> *)
- type Fact m = SingI m
- newtype PrimePower = PP (Nat, Nat)
- type SPrimePower = (Sing :: PrimePower -> *)
- type PPow pp = SingI pp
- data family Sing a
- data Nat :: *
- type NatC p = SingI p
- type family PrimeNat a
- type Prime p = (NatC p, PrimeNat p ~ True)
- toPP :: Nat -> Nat -> PrimePower
- sToPP :: forall t t. Sing t -> Sing t -> Sing (Apply (Apply ToPPSym0 t) t :: PrimePower)
- type family ToPP a a :: PrimePower
- ppToF :: PrimePower -> Factored
- sPpToF :: forall t. Sing t -> Sing (Apply PpToFSym0 t :: Factored)
- type family PpToF a :: Factored
- type PToF p = PpToF (ToPP p N1)
- unF :: Factored -> [PrimePower]
- sUnF :: forall t. Sing t -> Sing (Apply UnFSym0 t :: [PrimePower])
- type family UnF a :: [PrimePower]
- unPP :: PrimePower -> (Nat, Nat)
- sUnPP :: forall t. Sing t -> Sing (Apply UnPPSym0 t :: (Nat, Nat))
- type family UnPP a :: (Nat, Nat)
- primePP :: PrimePower -> Nat
- type family PrimePP a :: Nat
- exponentPP :: PrimePower -> Nat
- type family ExponentPP a :: Nat
- fPPMul :: PrimePower -> Factored -> Factored
- type family FPPMul a a :: Factored
- fMul :: Factored -> Factored -> Factored
- type family FMul a a :: Factored
- type * a b = FMul a b
- fDivides :: Factored -> Factored -> Bool
- type family FDivides a a :: Bool
- type Divides m m' = (Fact m, Fact m', FDivides m m' ~ True)
- fDiv :: Factored -> Factored -> Factored
- type family FDiv a a :: Factored
- type (/) a b = FDiv a b
- fGCD :: Factored -> Factored -> Factored
- type family FGCD a a :: Factored
- fLCM :: Factored -> Factored -> Factored
- type family FLCM a a :: Factored
- type Coprime m m' = FGCD m m' ~ F1
- fOddRadical :: Factored -> Factored
- type family FOddRadical a :: Factored
- pFree :: Nat -> Factored -> Factored
- type family PFree a a :: Factored
- transDivides :: forall k l m. Proxy k -> Proxy l -> Proxy m -> (k `Divides` l, l `Divides` m) :- (k `Divides` m)
- gcdDivides :: forall m1 m2 g. Proxy m1 -> Proxy m2 -> (Fact m1, Fact m2, g ~ FGCD m1 m2) :- (g `Divides` m1, g `Divides` m2)
- lcmDivides :: forall m1 m2 l. Proxy m1 -> Proxy m2 -> (Fact m1, Fact m2, l ~ FLCM m1 m2) :- (m1 `Divides` l, m2 `Divides` l)
- lcm2Divides :: forall m1 m2 l m. Proxy m1 -> Proxy m2 -> Proxy m -> (m1 `Divides` m, m2 `Divides` m, l ~ FLCM m1 m2) :- (m1 `Divides` l, m2 `Divides` l, FLCM m1 m2 `Divides` m)
- pSplitTheorems :: forall p m f. Proxy p -> Proxy m -> (NatC p, Fact m, f ~ PFree p m) :- (f `Divides` m, Coprime (PToF p) f)
- pFreeDivides :: forall p m m'. Proxy p -> Proxy m -> Proxy m' -> (NatC p, m `Divides` m') :- (PFree p m `Divides` PFree p m')
- (\\) :: a => (b -> r) -> (:-) a b -> r
- ppsFact :: forall m. Fact m => Tagged m [PP]
- valueFact :: Fact m => Tagged m Int
- totientFact :: Fact m => Tagged m Int
- valueHatFact :: Fact m => Tagged m Int
- radicalFact :: Fact m => Tagged m Int
- oddRadicalFact :: Fact m => Tagged m Int
- ppPPow :: forall pp. PPow pp => Tagged pp PP
- primePPow :: PPow pp => Tagged pp Int
- exponentPPow :: PPow pp => Tagged pp Int
- valuePPow :: PPow pp => Tagged pp Int
- totientPPow :: PPow pp => Tagged pp Int
- valueNatC :: forall p. NatC p => Tagged p Int
- valueHat :: Integral i => i -> i
- type PP = (Int, Int)
- ppToPP :: PrimePower -> PP
- valuePP :: PP -> Int
- totientPP :: PP -> Int
- radicalPP :: PP -> Int
- oddRadicalPP :: PP -> Int
- valuePPs :: [PP] -> Int
- totientPPs :: [PP] -> Int
- radicalPPs :: [PP] -> Int
- oddRadicalPPs :: [PP] -> Int
- type family F1
- type family F2
- type family F3
- type family F4
- type family F5
- type family F6
- type family F7
- type family F8
- type family F9
- type family F10
- type family F11
- type family F12
- type family F13
- type family F14
- type family F15
- type family F16
- type family F17
- type family F18
- type family F19
- type family F20
- type family F21
- type family F22
- type family F24
- type family F25
- type family F26
- type family F27
- type family F28
- type family F30
- type family F32
- type family F33
- type family F34
- type family F35
- type family F36
- type family F38
- type family F39
- type family F40
- type family F42
- type family F44
- type family F45
- type family F48
- type family F49
- type family F50
- type family F51
- type family F52
- type family F54
- type family F55
- type family F56
- type family F57
- type family F60
- type family F63
- type family F64
- type family F65
- type family F66
- type family F68
- type family F70
- type family F72
- type family F75
- type family F76
- type family F77
- type family F78
- type family F80
- type family F81
- type family F84
- type family F85
- type family F88
- type family F90
- type family F91
- type family F95
- type family F96
- type family F98
- type family F99
- type family F128
- type family F256
- type family F512
- type family F1024
- type family F2048
Factored natural numbers
F [PrimePower] |
Eq Factored Source | |
Show Factored Source | |
(Fact m, Integral i) => Reflects Factored m i Source | |
SingKind Factored (KProxy Factored) Source | |
SingI [PrimePower] n0 => SingI Factored (F n) Source | |
SEq Factored (KProxy Factored) Source | |
PEq Factored (KProxy Factored) Source | |
SDecide Factored (KProxy Factored) Source | |
data Sing Factored where Source | |
type (:/=) Factored x y = Not ((:==) Factored x y) | |
type (:==) Factored a0 b0 Source | |
type DemoteRep Factored (KProxy Factored) = Factored Source |
Prime powers
newtype PrimePower Source
Eq PrimePower Source | |
Show PrimePower Source | |
(PPow pp, Integral i) => Reflects PrimePower pp i Source | |
SingKind PrimePower (KProxy PrimePower) Source | |
SingI ((,) Nat Nat) n0 => SingI PrimePower (PP n) Source | |
SEq PrimePower (KProxy PrimePower) Source | |
PEq PrimePower (KProxy PrimePower) Source | |
SDecide PrimePower (KProxy PrimePower) Source | |
(PPow pp, (~) * zq (ZqBasic PrimePower pp z), PrimeField (ZPOf zq), Ring zq, Ring (ZPOf zq)) => ZPP (ZqBasic PrimePower pp z) Source | |
data Sing PrimePower where
| |
type (:/=) PrimePower x y = Not ((:==) PrimePower x y) | |
type (:==) PrimePower a0 b0 Source | |
type DemoteRep PrimePower (KProxy PrimePower) = PrimePower Source | |
type ZPOf (ZqBasic PrimePower pp z) = ZqBasic Nat (PrimePP pp) z Source |
type SPrimePower = (Sing :: PrimePower -> *) Source
type PPow pp = SingI pp Source
Kind-restricted synonym for SingI
. Use this in constraints
for types requiring a PrimePower
type.
data family Sing a
The singleton kind-indexed data family.
data Sing Bool where | |
data Sing Ordering where | |
data Sing Nat where | |
data Sing Symbol where
| |
data Sing () where | |
data Sing PrimePower where
| |
data Sing Factored where | |
data Sing Nat where | |
type MonomorphicRep Nat (Sing Nat) = Int | |
data Sing [a0] where | |
data Sing (Maybe a0) where | |
data Sing (TyFun k1 k2 -> *) = SLambda {} | |
data Sing (Either a0 b0) where | |
data Sing ((,) a0 b0) where | |
data Sing ((,,) a0 b0 c0) where | |
data Sing ((,,,) a0 b0 c0 d0) where | |
data Sing ((,,,,) a0 b0 c0 d0 e0) where | |
data Sing ((,,,,,) a0 b0 c0 d0 e0 f0) where | |
data Sing ((,,,,,,) a0 b0 c0 d0 e0 f0 g0) where |
Naturals
data Nat :: *
Eq Nat | |
Num Nat | |
Ord Nat | |
Show Nat | |
SingI Nat Z | |
(NatC a, Integral i) => Reflects Nat a i Source | |
SingKind Nat (KProxy Nat) | |
SingI Nat n0 => SingI Nat (S n0) | |
PNum Nat (KProxy Nat) | |
SNum Nat (KProxy Nat) | |
POrd Nat (KProxy Nat) | |
SOrd Nat (KProxy Nat) | |
SEq Nat (KProxy Nat) | |
PEq Nat (KProxy Nat) | |
SDecide Nat (KProxy Nat) | |
SuppressUnusedWarnings (TyFun Nat Nat -> *) FromInteger_1627442827Sym0 | |
SuppressUnusedWarnings (TyFun Nat (TyFun Nat Bool -> *) -> *) (:<<=$) | |
SuppressUnusedWarnings (TyFun Nat (TyFun Nat Bool -> *) -> *) TFHelper_1627439202Sym0 | |
SuppressUnusedWarnings (TyFun Nat (TyFun Nat Nat -> *) -> *) (:**$) | |
SuppressUnusedWarnings (TyFun Nat (TyFun Nat Nat -> *) -> *) TFHelper_1627442781Sym0 | |
SuppressUnusedWarnings (TyFun Nat (TyFun Nat Nat -> *) -> *) TFHelper_1627442756Sym0 | |
SuppressUnusedWarnings (TyFun Nat (TyFun Nat Nat -> *) -> *) TFHelper_1627442730Sym0 | |
SuppressUnusedWarnings (TyFun Nat (TyFun Nat Nat -> *) -> *) Min_1627439239Sym0 | |
SuppressUnusedWarnings (TyFun Nat (TyFun Nat Nat -> *) -> *) Max_1627439272Sym0 | |
SuppressUnusedWarnings (TyFun Nat Nat -> *) SSym0 | |
SuppressUnusedWarnings (TyFun Nat Nat -> *) Signum_1627442809Sym0 | |
SuppressUnusedWarnings (TyFun Nat Nat -> *) Abs_1627442796Sym0 | |
SuppressUnusedWarnings (Nat -> TyFun Nat Bool -> *) (:<<=$$) | |
SuppressUnusedWarnings (Nat -> TyFun Nat Bool -> *) TFHelper_1627439202Sym1 | |
SuppressUnusedWarnings (Nat -> TyFun Nat Nat -> *) (:**$$) | |
SuppressUnusedWarnings (Nat -> TyFun Nat Nat -> *) TFHelper_1627442781Sym1 | |
SuppressUnusedWarnings (Nat -> TyFun Nat Nat -> *) TFHelper_1627442756Sym1 | |
SuppressUnusedWarnings (Nat -> TyFun Nat Nat -> *) TFHelper_1627442730Sym1 | |
SuppressUnusedWarnings (Nat -> TyFun Nat Nat -> *) Min_1627439239Sym1 | |
SuppressUnusedWarnings (Nat -> TyFun Nat Nat -> *) Max_1627439272Sym1 | |
data Sing Nat where | |
type FromInteger Nat a0 = Apply Nat Nat FromInteger_1627442827Sym0 a0 | |
type Signum Nat a0 = Apply Nat Nat Signum_1627442809Sym0 a0 | |
type Abs Nat a0 = Apply Nat Nat Abs_1627442796Sym0 a0 | |
type Negate Nat arg0 = Apply Nat Nat (Negate_1627753616Sym0 Nat) arg0 | |
type (:*) Nat a0 a1 = Apply Nat Nat (Apply (TyFun Nat Nat -> *) Nat TFHelper_1627442781Sym0 a0) a1 | |
type (:-) Nat a0 a1 = Apply Nat Nat (Apply (TyFun Nat Nat -> *) Nat TFHelper_1627442756Sym0 a0) a1 | |
type (:+) Nat a0 a1 = Apply Nat Nat (Apply (TyFun Nat Nat -> *) Nat TFHelper_1627442730Sym0 a0) a1 | |
type Min Nat a0 a1 = Apply Nat Nat (Apply (TyFun Nat Nat -> *) Nat Min_1627439239Sym0 a0) a1 | |
type Max Nat a0 a1 = Apply Nat Nat (Apply (TyFun Nat Nat -> *) Nat Max_1627439272Sym0 a0) a1 | |
type (:>=) Nat arg0 arg1 = Apply Bool Nat (Apply (TyFun Nat Bool -> *) Nat (TFHelper_1627641632Sym0 Nat) arg0) arg1 | |
type (:>) Nat arg0 arg1 = Apply Bool Nat (Apply (TyFun Nat Bool -> *) Nat (TFHelper_1627641599Sym0 Nat) arg0) arg1 | |
type (:<=) Nat a0 a1 = Apply Bool Nat (Apply (TyFun Nat Bool -> *) Nat TFHelper_1627439202Sym0 a0) a1 | |
type (:<) Nat arg0 arg1 = Apply Bool Nat (Apply (TyFun Nat Bool -> *) Nat (TFHelper_1627641533Sym0 Nat) arg0) arg1 | |
type Compare Nat arg0 arg1 = Apply Ordering Nat (Apply (TyFun Nat Ordering -> *) Nat (Compare_1627641500Sym0 Nat) arg0) arg1 | |
type (:/=) Nat x y = Not ((:==) Nat x y) | |
type (:==) Nat a0 b0 = Equals_1627433666 a0 b0 | |
type Apply Nat Nat FromInteger_1627442827Sym0 l0 = FromInteger_1627442827Sym1 l0 | |
type Apply Nat Nat SSym0 l0 = SSym1 l0 | |
type Apply Nat Nat Signum_1627442809Sym0 l0 = Signum_1627442809Sym1 l0 | |
type Apply Nat Nat Abs_1627442796Sym0 l0 = Abs_1627442796Sym1 l0 | |
type Apply Bool Nat ((:<<=$$) l1) l0 = (:<<=$$$) l1 l0 | |
type Apply Bool Nat (TFHelper_1627439202Sym1 l1) l0 = TFHelper_1627439202Sym2 l1 l0 | |
type Apply Nat Nat ((:**$$) l1) l0 = (:**$$$) l1 l0 | |
type Apply Nat Nat (TFHelper_1627442781Sym1 l1) l0 = TFHelper_1627442781Sym2 l1 l0 | |
type Apply Nat Nat (TFHelper_1627442756Sym1 l1) l0 = TFHelper_1627442756Sym2 l1 l0 | |
type Apply Nat Nat (TFHelper_1627442730Sym1 l1) l0 = TFHelper_1627442730Sym2 l1 l0 | |
type Apply Nat Nat (Min_1627439239Sym1 l1) l0 = Min_1627439239Sym2 l1 l0 | |
type Apply Nat Nat (Max_1627439272Sym1 l1) l0 = Max_1627439272Sym2 l1 l0 | |
type DemoteRep Nat (KProxy Nat) = Nat | |
type MonomorphicRep Nat (Sing Nat) = Int | |
type CharOf * (ZqBasic Nat p z) = p Source | |
type Apply (TyFun Nat Bool -> *) Nat (:<<=$) l0 = (:<<=$$) l0 | |
type Apply (TyFun Nat Bool -> *) Nat TFHelper_1627439202Sym0 l0 = TFHelper_1627439202Sym1 l0 | |
type Apply (TyFun Nat Nat -> *) Nat (:**$) l0 = (:**$$) l0 | |
type Apply (TyFun Nat Nat -> *) Nat TFHelper_1627442781Sym0 l0 = TFHelper_1627442781Sym1 l0 | |
type Apply (TyFun Nat Nat -> *) Nat TFHelper_1627442756Sym0 l0 = TFHelper_1627442756Sym1 l0 | |
type Apply (TyFun Nat Nat -> *) Nat TFHelper_1627442730Sym0 l0 = TFHelper_1627442730Sym1 l0 | |
type Apply (TyFun Nat Nat -> *) Nat Min_1627439239Sym0 l0 = Min_1627439239Sym1 l0 | |
type Apply (TyFun Nat Nat -> *) Nat Max_1627439272Sym0 l0 = Max_1627439272Sym1 l0 |
PrimeNat arg_1627477538 = Case_1627478044 arg_1627477538 arg_1627477538 |
Constructors
toPP :: Nat -> Nat -> PrimePower Source
type family ToPP a a :: PrimePower Source
ToPP arg_1627477532 arg_1627477534 = Case_1627478100 arg_1627477532 arg_1627477534 (Apply (Apply Tuple2Sym0 arg_1627477532) arg_1627477534) |
ppToF :: PrimePower -> Factored Source
Unwrappers
unF :: Factored -> [PrimePower] Source
type family UnF a :: [PrimePower] Source
unPP :: PrimePower -> (Nat, Nat) Source
primePP :: PrimePower -> Nat Source
exponentPP :: PrimePower -> Nat Source
type family ExponentPP a :: Nat Source
Arithmetic operations
fPPMul :: PrimePower -> Factored -> Factored Source
type Divides m m' = (Fact m, Fact m', FDivides m m' ~ True) Source
Constraint synonym for divisibility of Factored
types
fOddRadical :: Factored -> Factored Source
type family FOddRadical a :: Factored Source
FOddRadical (F pps) = Apply FSym0 (Apply PpsOddRadSym0 pps) |
Coercions
transDivides :: forall k l m. Proxy k -> Proxy l -> Proxy m -> (k `Divides` l, l `Divides` m) :- (k `Divides` m) Source
Entails constraint for transitivity of division, i.e.
if k|l
and l|m
, then k|m
.
gcdDivides :: forall m1 m2 g. Proxy m1 -> Proxy m2 -> (Fact m1, Fact m2, g ~ FGCD m1 m2) :- (g `Divides` m1, g `Divides` m2) Source
Entails constraint for divisibility by GCD, i.e.
if g=GCD(m1,m2)
, then g|m1
and g|m2
.
lcmDivides :: forall m1 m2 l. Proxy m1 -> Proxy m2 -> (Fact m1, Fact m2, l ~ FLCM m1 m2) :- (m1 `Divides` l, m2 `Divides` l) Source
Entails constraint for LCM divisibility, i.e.
if l=LCM(m1,m2)
, then m1|l
and m2|l
.
lcm2Divides :: forall m1 m2 l m. Proxy m1 -> Proxy m2 -> Proxy m -> (m1 `Divides` m, m2 `Divides` m, l ~ FLCM m1 m2) :- (m1 `Divides` l, m2 `Divides` l, FLCM m1 m2 `Divides` m) Source
Entails constraint for LCM divisibility, i.e.
the LCM of two divisors of m
also divides m
.
pSplitTheorems :: forall p m f. Proxy p -> Proxy m -> (NatC p, Fact m, f ~ PFree p m) :- (f `Divides` m, Coprime (PToF p) f) Source
Entails basic facts for p
-free division, i.e.
if f
is m
after removing all p
-factors, then f|m
and
gcd(f,p)=1
pFreeDivides :: forall p m m'. Proxy p -> Proxy m -> Proxy m' -> (NatC p, m `Divides` m') :- (PFree p m `Divides` PFree p m') Source
Entails basic facts for p
-free division, i.e.,
if m|m'
, then p-free(m) | p-free(m')
(\\) :: a => (b -> r) -> (:-) a b -> r infixl 1
Given that a :- b
, derive something that needs a context b
, using the context a
Operations on factored integers and naturals
ppsFact :: forall m. Fact m => Tagged m [PP] Source
Value-level prime-power factorization tagged by a Factored
type.
valueHatFact :: Fact m => Tagged m Int Source
Int
representing the "hat" of a Factored
type's value m
:
m
, if m
is odd, or m/2
otherwise.
radicalFact :: Fact m => Tagged m Int Source
Int
representing the radical (product of prime divisors)
of a Factored
type
oddRadicalFact :: Fact m => Tagged m Int Source
Int
representing the odd radical (product of odd prime divisors)
of a Factored
type
exponentPPow :: PPow pp => Tagged pp Int Source
Reflects the exponent component of a PrimePower
type
totientPPow :: PPow pp => Tagged pp Int Source
Int
representing the totient of a PrimePower
type's value
ppToPP :: PrimePower -> PP Source
Converts a Nat
prime-power pair to an Int
prime-power pair
oddRadicalPP :: PP -> Int Source
The odd radical of a prime-power pair (p,_): p if p is odd, 1 if p==2
totientPPs :: [PP] -> Int Source
Product of totients of individual PP
s
radicalPPs :: [PP] -> Int Source
Product of radicals of individual PP
s
oddRadicalPPs :: [PP] -> Int Source
Product of odd radicals of individual PP
s