module Factory.Data.PrimeFactors(
Factors,
insert',
product',
reduce,
(>*<),
(>/<),
(>^)
) where
import qualified Control.Arrow
import Control.Arrow((&&&))
import qualified Data.List
import qualified Data.Ord
import qualified Factory.Math.DivideAndConquer as Math.DivideAndConquer
import qualified Factory.Data.Exponential as Data.Exponential
import Factory.Data.Exponential((<^), (=~))
import qualified ToolShed.Data.List
infixl 7 >/<, >*<
infixr 8 >^
type Factors base exponent = [Data.Exponential.Exponential base exponent]
reduce :: (Ord base, Num exponent, Ord exponent) => Factors base exponent -> Factors base exponent
reduce :: Factors base exponent -> Factors base exponent
reduce = Factors base exponent -> Factors base exponent
forall base exponent.
(Eq base, Num exponent) =>
Factors base exponent -> Factors base exponent
reduceSorted (Factors base exponent -> Factors base exponent)
-> (Factors base exponent -> Factors base exponent)
-> Factors base exponent
-> Factors base exponent
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Factors base exponent -> Factors base exponent
forall a. Ord a => [a] -> [a]
Data.List.sort
reduceSorted :: (Eq base, Num exponent) => Factors base exponent -> Factors base exponent
reduceSorted :: Factors base exponent -> Factors base exponent
reduceSorted [] = []
reduceSorted (Exponential base exponent
x : Factors base exponent
xs)
| Factors base exponent -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null Factors base exponent
matched = Exponential base exponent
x Exponential base exponent
-> Factors base exponent -> Factors base exponent
forall a. a -> [a] -> [a]
: Factors base exponent -> Factors base exponent
forall base exponent.
(Eq base, Num exponent) =>
Factors base exponent -> Factors base exponent
reduceSorted Factors base exponent
remainder
| Bool
otherwise = (exponent -> exponent)
-> Exponential base exponent -> Exponential base exponent
forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (d, b) (d, c)
Control.Arrow.second (exponent -> exponent -> exponent
forall a. Num a => a -> a -> a
+ Factors base exponent -> exponent
forall exponent base.
Num exponent =>
Factors base exponent -> exponent
sumExponents Factors base exponent
matched) Exponential base exponent
x Exponential base exponent
-> Factors base exponent -> Factors base exponent
forall a. a -> [a] -> [a]
: Factors base exponent -> Factors base exponent
forall base exponent.
(Eq base, Num exponent) =>
Factors base exponent -> Factors base exponent
reduceSorted Factors base exponent
remainder
where
(Factors base exponent
matched, Factors base exponent
remainder) = (Exponential base exponent -> Bool)
-> Factors base exponent
-> (Factors base exponent, Factors base exponent)
forall a. (a -> Bool) -> [a] -> ([a], [a])
span (Exponential base exponent -> Exponential base exponent -> Bool
forall base exponent.
Eq base =>
Exponential base exponent -> Exponential base exponent -> Bool
=~ Exponential base exponent
x) Factors base exponent
xs
insert' :: (Ord base, Num exponent) => Data.Exponential.Exponential base exponent -> Factors base exponent -> Factors base exponent
insert' :: Exponential base exponent
-> Factors base exponent -> Factors base exponent
insert' Exponential base exponent
e [] = [Exponential base exponent
e]
insert' Exponential base exponent
e l :: Factors base exponent
l@(Exponential base exponent
x : Factors base exponent
xs) = case (Exponential base exponent -> base)
-> Exponential base exponent
-> Exponential base exponent
-> Ordering
forall a b. Ord a => (b -> a) -> b -> b -> Ordering
Data.Ord.comparing Exponential base exponent -> base
forall base exponent. Exponential base exponent -> base
Data.Exponential.getBase Exponential base exponent
e Exponential base exponent
x of
Ordering
LT -> Exponential base exponent
e Exponential base exponent
-> Factors base exponent -> Factors base exponent
forall a. a -> [a] -> [a]
: Factors base exponent
l
Ordering
GT -> Exponential base exponent
x Exponential base exponent
-> Factors base exponent -> Factors base exponent
forall a. a -> [a] -> [a]
: Exponential base exponent
-> Factors base exponent -> Factors base exponent
forall base exponent.
(Ord base, Num exponent) =>
Exponential base exponent
-> Factors base exponent -> Factors base exponent
insert' Exponential base exponent
e Factors base exponent
xs
Ordering
_ -> (exponent -> exponent)
-> Exponential base exponent -> Exponential base exponent
forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (d, b) (d, c)
Control.Arrow.second (exponent -> exponent -> exponent
forall a. Num a => a -> a -> a
+ Exponential base exponent -> exponent
forall base exponent. Exponential base exponent -> exponent
Data.Exponential.getExponent Exponential base exponent
e) Exponential base exponent
x Exponential base exponent
-> Factors base exponent -> Factors base exponent
forall a. a -> [a] -> [a]
: Factors base exponent
xs
(>*<) :: (Ord base, Num exponent, Ord exponent) => Factors base exponent -> Factors base exponent -> Factors base exponent
Factors base exponent
l >*< :: Factors base exponent
-> Factors base exponent -> Factors base exponent
>*< Factors base exponent
r = Factors base exponent -> Factors base exponent
forall base exponent.
(Eq base, Num exponent) =>
Factors base exponent -> Factors base exponent
reduceSorted (Factors base exponent -> Factors base exponent)
-> Factors base exponent -> Factors base exponent
forall a b. (a -> b) -> a -> b
$ Factors base exponent
-> Factors base exponent -> Factors base exponent
forall a. Ord a => [a] -> [a] -> [a]
ToolShed.Data.List.merge Factors base exponent
l Factors base exponent
r
invert :: Num exponent => Factors base exponent -> Factors base exponent
invert :: Factors base exponent -> Factors base exponent
invert = (Exponential base exponent -> Exponential base exponent)
-> Factors base exponent -> Factors base exponent
forall a b. (a -> b) -> [a] -> [b]
map Exponential base exponent -> Exponential base exponent
forall exponent base.
Num exponent =>
Exponential base exponent -> Exponential base exponent
Data.Exponential.invert
(>/<) :: (Integral base, Integral exponent)
=> Factors base exponent
-> Factors base exponent
-> (Factors base exponent, Factors base exponent)
Factors base exponent
numerator >/< :: Factors base exponent
-> Factors base exponent
-> (Factors base exponent, Factors base exponent)
>/< Factors base exponent
denominator = (Exponential base exponent -> Bool)
-> Factors base exponent -> Factors base exponent
forall a. (a -> Bool) -> [a] -> [a]
filter (
(exponent -> exponent -> Bool
forall a. Ord a => a -> a -> Bool
> exponent
0) (exponent -> Bool)
-> (Exponential base exponent -> exponent)
-> Exponential base exponent
-> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Exponential base exponent -> exponent
forall base exponent. Exponential base exponent -> exponent
Data.Exponential.getExponent
) (Factors base exponent -> Factors base exponent)
-> (Factors base exponent -> Factors base exponent)
-> Factors base exponent
-> (Factors base exponent, Factors base exponent)
forall (a :: * -> * -> *) b c c'.
Arrow a =>
a b c -> a b c' -> a b (c, c')
&&& Factors base exponent -> Factors base exponent
forall exponent base.
Num exponent =>
Factors base exponent -> Factors base exponent
invert (Factors base exponent -> Factors base exponent)
-> (Factors base exponent -> Factors base exponent)
-> Factors base exponent
-> Factors base exponent
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Exponential base exponent -> Bool)
-> Factors base exponent -> Factors base exponent
forall a. (a -> Bool) -> [a] -> [a]
filter (
(exponent -> exponent -> Bool
forall a. Ord a => a -> a -> Bool
< exponent
0) (exponent -> Bool)
-> (Exponential base exponent -> exponent)
-> Exponential base exponent
-> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Exponential base exponent -> exponent
forall base exponent. Exponential base exponent -> exponent
Data.Exponential.getExponent
) (Factors base exponent
-> (Factors base exponent, Factors base exponent))
-> Factors base exponent
-> (Factors base exponent, Factors base exponent)
forall a b. (a -> b) -> a -> b
$ Factors base exponent
numerator Factors base exponent
-> Factors base exponent -> Factors base exponent
forall base exponent.
(Ord base, Num exponent, Ord exponent) =>
Factors base exponent
-> Factors base exponent -> Factors base exponent
>*< Factors base exponent -> Factors base exponent
forall exponent base.
Num exponent =>
Factors base exponent -> Factors base exponent
invert Factors base exponent
denominator
(>^) :: Num exponent => Factors base exponent -> exponent -> Factors base exponent
Factors base exponent
factors >^ :: Factors base exponent -> exponent -> Factors base exponent
>^ exponent
power = (Exponential base exponent -> Exponential base exponent)
-> Factors base exponent -> Factors base exponent
forall a b. (a -> b) -> [a] -> [b]
map (Exponential base exponent -> exponent -> Exponential base exponent
forall exponent base.
Num exponent =>
Exponential base exponent -> exponent -> Exponential base exponent
<^ exponent
power) Factors base exponent
factors
sumExponents :: Num exponent => Factors base exponent -> exponent
sumExponents :: Factors base exponent -> exponent
sumExponents = (Exponential base exponent -> exponent -> exponent)
-> exponent -> Factors base exponent -> exponent
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (exponent -> exponent -> exponent
forall a. Num a => a -> a -> a
(+) (exponent -> exponent -> exponent)
-> (Exponential base exponent -> exponent)
-> Exponential base exponent
-> exponent
-> exponent
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Exponential base exponent -> exponent
forall base exponent. Exponential base exponent -> exponent
Data.Exponential.getExponent) exponent
0
product' :: (Num base, Integral exponent)
=> Math.DivideAndConquer.BisectionRatio
-> Math.DivideAndConquer.MinLength
-> Factors base exponent
-> base
product' :: BisectionRatio -> MinLength -> Factors base exponent -> base
product' BisectionRatio
bisectionRatio MinLength
minLength = BisectionRatio -> MinLength -> [base] -> base
forall n. Num n => BisectionRatio -> MinLength -> [n] -> n
Math.DivideAndConquer.product' BisectionRatio
bisectionRatio MinLength
minLength ([base] -> base)
-> (Factors base exponent -> [base])
-> Factors base exponent
-> base
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Exponential base exponent -> base)
-> Factors base exponent -> [base]
forall a b. (a -> b) -> [a] -> [b]
map Exponential base exponent -> base
forall base exponent.
(Num base, Integral exponent) =>
Exponential base exponent -> base
Data.Exponential.evaluate