{-# LANGUAGE CPP #-}
module Factory.Data.Polynomial(
Polynomial,
zero,
one,
evaluate,
getDegree,
getLeadingTerm,
lift,
mod',
normalise,
raiseModulo,
realCoefficientsToFrac,
terms,
mkConstant,
mkLinear,
mkPolynomial,
(*=),
areCongruentModulo,
inAscendingOrder,
inDescendingOrder,
isMonic,
isMonomial,
isNormalised,
isPolynomial,
isZero
) where
import Control.Arrow((&&&))
import qualified Control.Arrow
import qualified Data.List
import Factory.Data.Monomial((<*>), (</>), (<=>), (=~))
import qualified Factory.Data.Monomial as Data.Monomial
import qualified Factory.Data.QuotientRing as Data.QuotientRing
import Factory.Data.Ring((=*=), (=+=), (=-=))
import qualified Factory.Data.Ring as Data.Ring
#if MIN_VERSION_base(4,8,0)
import Prelude hiding ((<*>))
#endif
infixl 7 *=
type MonomialList coefficient exponent = [Data.Monomial.Monomial coefficient exponent]
newtype Polynomial coefficient exponent = MkPolynomial {
Polynomial coefficient exponent
-> MonomialList coefficient exponent
getMonomialList :: MonomialList coefficient exponent
} deriving (Polynomial coefficient exponent
-> Polynomial coefficient exponent -> Bool
(Polynomial coefficient exponent
-> Polynomial coefficient exponent -> Bool)
-> (Polynomial coefficient exponent
-> Polynomial coefficient exponent -> Bool)
-> Eq (Polynomial coefficient exponent)
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
forall coefficient exponent.
(Eq coefficient, Eq exponent) =>
Polynomial coefficient exponent
-> Polynomial coefficient exponent -> Bool
/= :: Polynomial coefficient exponent
-> Polynomial coefficient exponent -> Bool
$c/= :: forall coefficient exponent.
(Eq coefficient, Eq exponent) =>
Polynomial coefficient exponent
-> Polynomial coefficient exponent -> Bool
== :: Polynomial coefficient exponent
-> Polynomial coefficient exponent -> Bool
$c== :: forall coefficient exponent.
(Eq coefficient, Eq exponent) =>
Polynomial coefficient exponent
-> Polynomial coefficient exponent -> Bool
Eq, Int -> Polynomial coefficient exponent -> ShowS
[Polynomial coefficient exponent] -> ShowS
Polynomial coefficient exponent -> String
(Int -> Polynomial coefficient exponent -> ShowS)
-> (Polynomial coefficient exponent -> String)
-> ([Polynomial coefficient exponent] -> ShowS)
-> Show (Polynomial coefficient exponent)
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
forall coefficient exponent.
(Show coefficient, Show exponent) =>
Int -> Polynomial coefficient exponent -> ShowS
forall coefficient exponent.
(Show coefficient, Show exponent) =>
[Polynomial coefficient exponent] -> ShowS
forall coefficient exponent.
(Show coefficient, Show exponent) =>
Polynomial coefficient exponent -> String
showList :: [Polynomial coefficient exponent] -> ShowS
$cshowList :: forall coefficient exponent.
(Show coefficient, Show exponent) =>
[Polynomial coefficient exponent] -> ShowS
show :: Polynomial coefficient exponent -> String
$cshow :: forall coefficient exponent.
(Show coefficient, Show exponent) =>
Polynomial coefficient exponent -> String
showsPrec :: Int -> Polynomial coefficient exponent -> ShowS
$cshowsPrec :: forall coefficient exponent.
(Show coefficient, Show exponent) =>
Int -> Polynomial coefficient exponent -> ShowS
Show)
instance (
Eq c,
Num c,
Num e,
Ord e
) => Data.Ring.Ring (Polynomial c e) where
MkPolynomial [] =*= :: Polynomial c e -> Polynomial c e -> Polynomial c e
=*= Polynomial c e
_ = Polynomial c e
forall c e. Polynomial c e
zero
Polynomial c e
_ =*= MkPolynomial [] = Polynomial c e
forall c e. Polynomial c e
zero
Polynomial c e
polynomialL =*= Polynomial c e
polynomialR
| Polynomial c e -> Int
forall c e. Polynomial c e -> Int
terms Polynomial c e
polynomialL Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Polynomial c e -> Int
forall c e. Polynomial c e -> Int
terms Polynomial c e
polynomialR = Polynomial c e
polynomialL Polynomial c e -> Polynomial c e -> Polynomial c e
forall c e.
(Num c, Num e, Ord e, Eq c) =>
Polynomial c e -> Polynomial c e -> Polynomial c e
`times` Polynomial c e
polynomialR
| Bool
otherwise = Polynomial c e
polynomialR Polynomial c e -> Polynomial c e -> Polynomial c e
forall c e.
(Num c, Num e, Ord e, Eq c) =>
Polynomial c e -> Polynomial c e -> Polynomial c e
`times` Polynomial c e
polynomialL
where
Polynomial c e
l times :: Polynomial c e -> Polynomial c e -> Polynomial c e
`times` Polynomial c e
r = {-# SCC "times" #-} BisectionRatio -> Int -> [Polynomial c e] -> Polynomial c e
forall r. Ring r => BisectionRatio -> Int -> [r] -> r
Data.Ring.sum' (BisectionRatio -> BisectionRatio
forall a. Fractional a => a -> a
recip BisectionRatio
2) Int
10 ([Polynomial c e] -> Polynomial c e)
-> ([Monomial c e] -> [Polynomial c e])
-> [Monomial c e]
-> Polynomial c e
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Monomial c e -> Polynomial c e)
-> [Monomial c e] -> [Polynomial c e]
forall a b. (a -> b) -> [a] -> [b]
map (Polynomial c e
l Polynomial c e -> Monomial c e -> Polynomial c e
forall c e.
(Eq c, Num c, Num e) =>
Polynomial c e -> Monomial c e -> Polynomial c e
*=) ([Monomial c e] -> Polynomial c e)
-> [Monomial c e] -> Polynomial c e
forall a b. (a -> b) -> a -> b
$ Polynomial c e -> [Monomial c e]
forall coefficient exponent.
Polynomial coefficient exponent
-> MonomialList coefficient exponent
getMonomialList Polynomial c e
r
MkPolynomial [] =+= :: Polynomial c e -> Polynomial c e -> Polynomial c e
=+= Polynomial c e
p = Polynomial c e
p
Polynomial c e
p =+= MkPolynomial [] = Polynomial c e
p
MkPolynomial [Monomial c e]
listL =+= MkPolynomial [Monomial c e]
listR = {-# SCC "merge" #-} [Monomial c e] -> Polynomial c e
forall coefficient exponent.
MonomialList coefficient exponent
-> Polynomial coefficient exponent
MkPolynomial ([Monomial c e] -> Polynomial c e)
-> [Monomial c e] -> Polynomial c e
forall a b. (a -> b) -> a -> b
$ [Monomial c e] -> [Monomial c e] -> [Monomial c e]
forall e a.
(Ord e, Num a, Eq a) =>
[(a, e)] -> [(a, e)] -> [(a, e)]
merge [Monomial c e]
listL [Monomial c e]
listR where
merge :: [(a, e)] -> [(a, e)] -> [(a, e)]
merge [] [(a, e)]
r = [(a, e)]
r
merge [(a, e)]
l [] = [(a, e)]
l
merge l :: [(a, e)]
l@((a, e)
lh : [(a, e)]
ls) r :: [(a, e)]
r@((a, e)
rh : [(a, e)]
rs) = case (a, e)
lh (a, e) -> (a, e) -> Ordering
forall e c. Ord e => Monomial c e -> Monomial c e -> Ordering
<=> (a, e)
rh of
Ordering
GT -> (a, e)
lh (a, e) -> [(a, e)] -> [(a, e)]
forall a. a -> [a] -> [a]
: [(a, e)] -> [(a, e)] -> [(a, e)]
merge [(a, e)]
ls [(a, e)]
r
Ordering
LT -> (a, e)
rh (a, e) -> [(a, e)] -> [(a, e)]
forall a. a -> [a] -> [a]
: [(a, e)] -> [(a, e)] -> [(a, e)]
merge [(a, e)]
l [(a, e)]
rs
Ordering
_ -> case (a, e)
lh (a, e) -> a -> (a, e)
forall c e. Num c => Monomial c e -> c -> Monomial c e
`Data.Monomial.shiftCoefficient` (a, e) -> a
forall c e. Monomial c e -> c
Data.Monomial.getCoefficient (a, e)
rh of
(a
0, e
_) -> [(a, e)] -> [(a, e)] -> [(a, e)]
merge [(a, e)]
ls [(a, e)]
rs
(a, e)
monomial -> (a, e)
monomial (a, e) -> [(a, e)] -> [(a, e)]
forall a. a -> [a] -> [a]
: [(a, e)] -> [(a, e)] -> [(a, e)]
merge [(a, e)]
ls [(a, e)]
rs
additiveInverse :: Polynomial c e -> Polynomial c e
additiveInverse = ([Monomial c e] -> [Monomial c e])
-> Polynomial c e -> Polynomial c e
forall c1 e1 c2 e2.
(MonomialList c1 e1 -> MonomialList c2 e2)
-> Polynomial c1 e1 -> Polynomial c2 e2
lift (Monomial c e -> Monomial c e
forall c e. Num c => Monomial c e -> Monomial c e
Data.Monomial.negateCoefficient (Monomial c e -> Monomial c e) -> [Monomial c e] -> [Monomial c e]
forall a b. (a -> b) -> [a] -> [b]
`map`)
multiplicativeIdentity :: Polynomial c e
multiplicativeIdentity = Polynomial c e
forall c e. (Eq c, Num c, Num e) => Polynomial c e
one
additiveIdentity :: Polynomial c e
additiveIdentity = Polynomial c e
forall c e. Polynomial c e
zero
square :: Polynomial c e -> Polynomial c e
square (MkPolynomial []) = Polynomial c e
forall c e. Polynomial c e
zero
square Polynomial c e
p = BisectionRatio -> Int -> [Polynomial c e] -> Polynomial c e
forall r. Ring r => BisectionRatio -> Int -> [r] -> r
Data.Ring.sum' (BisectionRatio -> BisectionRatio
forall a. Fractional a => a -> a
recip BisectionRatio
2) Int
10 ([Polynomial c e] -> Polynomial c e)
-> [Polynomial c e] -> Polynomial c e
forall a b. (a -> b) -> a -> b
$ Polynomial c e
diagonal Polynomial c e -> [Polynomial c e] -> [Polynomial c e]
forall a. a -> [a] -> [a]
: [Polynomial c e]
corners where
diagonal :: Polynomial c e
diagonal = {-# SCC "diagonal" #-} (Monomial c e -> Monomial c e) -> [Monomial c e] -> [Monomial c e]
forall a b. (a -> b) -> [a] -> [b]
map Monomial c e -> Monomial c e
forall c e. (Num c, Num e) => Monomial c e -> Monomial c e
Data.Monomial.square ([Monomial c e] -> [Monomial c e])
-> Polynomial c e -> Polynomial c e
forall c1 e1 c2 e2.
(MonomialList c1 e1 -> MonomialList c2 e2)
-> Polynomial c1 e1 -> Polynomial c2 e2
`lift` Polynomial c e
p
corners :: [Polynomial c e]
corners = {-# SCC "corners" #-} ([Polynomial c e] -> [Monomial c e] -> [Polynomial c e])
-> ([Polynomial c e], [Monomial c e]) -> [Polynomial c e]
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry (
(Polynomial c e -> Monomial c e -> Polynomial c e)
-> [Polynomial c e] -> [Monomial c e] -> [Polynomial c e]
forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
zipWith Polynomial c e -> Monomial c e -> Polynomial c e
forall c e.
(Eq c, Num c, Num e) =>
Polynomial c e -> Monomial c e -> Polynomial c e
(*=)
) (([Polynomial c e], [Monomial c e]) -> [Polynomial c e])
-> ([Polynomial c e], [Monomial c e]) -> [Polynomial c e]
forall a b. (a -> b) -> a -> b
$ ([Monomial c e] -> Polynomial c e)
-> [[Monomial c e]] -> [Polynomial c e]
forall a b. (a -> b) -> [a] -> [b]
map [Monomial c e] -> Polynomial c e
forall coefficient exponent.
MonomialList coefficient exponent
-> Polynomial coefficient exponent
MkPolynomial ([[Monomial c e]] -> [Polynomial c e])
-> ([Monomial c e] -> [[Monomial c e]])
-> [Monomial c e]
-> [Polynomial c e]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [[Monomial c e]] -> [[Monomial c e]]
forall a. [a] -> [a]
init ([[Monomial c e]] -> [[Monomial c e]])
-> ([Monomial c e] -> [[Monomial c e]])
-> [Monomial c e]
-> [[Monomial c e]]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Monomial c e] -> [[Monomial c e]]
forall a. [a] -> [[a]]
Data.List.tails ([Monomial c e] -> [[Monomial c e]])
-> ([Monomial c e] -> [Monomial c e])
-> [Monomial c e]
-> [[Monomial c e]]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Monomial c e] -> [Monomial c e]
forall a. [a] -> [a]
tail ([Monomial c e] -> [Polynomial c e])
-> ([Monomial c e] -> [Monomial c e])
-> [Monomial c e]
-> ([Polynomial c e], [Monomial c e])
forall (a :: * -> * -> *) b c c'.
Arrow a =>
a b c -> a b c' -> a b (c, c')
&&& (Monomial c e -> Monomial c e) -> [Monomial c e] -> [Monomial c e]
forall a b. (a -> b) -> [a] -> [b]
map Monomial c e -> Monomial c e
forall c e. Num c => Monomial c e -> Monomial c e
Data.Monomial.double ([Monomial c e] -> ([Polynomial c e], [Monomial c e]))
-> [Monomial c e] -> ([Polynomial c e], [Monomial c e])
forall a b. (a -> b) -> a -> b
$ Polynomial c e -> [Monomial c e]
forall coefficient exponent.
Polynomial coefficient exponent
-> MonomialList coefficient exponent
getMonomialList Polynomial c e
p
instance (
Eq c,
Fractional c,
Num e,
Ord e
) => Data.QuotientRing.QuotientRing (Polynomial c e) where
Polynomial c e
_ quotRem' :: Polynomial c e
-> Polynomial c e -> (Polynomial c e, Polynomial c e)
`quotRem'` MkPolynomial [] = String -> (Polynomial c e, Polynomial c e)
forall a. HasCallStack => String -> a
error String
"Factory.Data.Polynomial.quotRem':\tzero denominator."
Polynomial c e
polynomialN `quotRem'` Polynomial c e
polynomialD = Polynomial c e -> (Polynomial c e, Polynomial c e)
longDivide Polynomial c e
polynomialN where
longDivide :: Polynomial c e -> (Polynomial c e, Polynomial c e)
longDivide (MkPolynomial []) = (Polynomial c e
forall c e. Polynomial c e
zero, Polynomial c e
forall c e. Polynomial c e
zero)
longDivide Polynomial c e
numerator
| Monomial c e -> e
forall c e. Monomial c e -> e
Data.Monomial.getExponent Monomial c e
quotient e -> e -> Bool
forall a. Ord a => a -> a -> Bool
< e
0 = (Polynomial c e
forall c e. Polynomial c e
zero, Polynomial c e
numerator)
| Bool
otherwise = (Polynomial c e -> Polynomial c e)
-> (Polynomial c e, Polynomial c e)
-> (Polynomial c e, Polynomial c e)
forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (b, d) (c, d)
Control.Arrow.first (([Monomial c e] -> [Monomial c e])
-> Polynomial c e -> Polynomial c e
forall c1 e1 c2 e2.
(MonomialList c1 e1 -> MonomialList c2 e2)
-> Polynomial c1 e1 -> Polynomial c2 e2
lift (Monomial c e
quotient Monomial c e -> [Monomial c e] -> [Monomial c e]
forall a. a -> [a] -> [a]
:)) ((Polynomial c e, Polynomial c e)
-> (Polynomial c e, Polynomial c e))
-> (Polynomial c e, Polynomial c e)
-> (Polynomial c e, Polynomial c e)
forall a b. (a -> b) -> a -> b
$ Polynomial c e -> (Polynomial c e, Polynomial c e)
longDivide (Polynomial c e
numerator Polynomial c e -> Polynomial c e -> Polynomial c e
forall r. Ring r => r -> r -> r
=-= Polynomial c e
polynomialD Polynomial c e -> Monomial c e -> Polynomial c e
forall c e.
(Eq c, Num c, Num e) =>
Polynomial c e -> Monomial c e -> Polynomial c e
*= Monomial c e
quotient )
where
quotient :: Monomial c e
quotient = Polynomial c e -> Monomial c e
forall c e. Polynomial c e -> Monomial c e
getLeadingTerm Polynomial c e
numerator Monomial c e -> Monomial c e -> Monomial c e
forall c e.
(Eq c, Fractional c, Num e) =>
Monomial c e -> Monomial c e -> Monomial c e
</> Polynomial c e -> Monomial c e
forall c e. Polynomial c e -> Monomial c e
getLeadingTerm Polynomial c e
polynomialD
lift :: (MonomialList c1 e1 -> MonomialList c2 e2) -> Polynomial c1 e1 -> Polynomial c2 e2
lift :: (MonomialList c1 e1 -> MonomialList c2 e2)
-> Polynomial c1 e1 -> Polynomial c2 e2
lift MonomialList c1 e1 -> MonomialList c2 e2
transform = MonomialList c2 e2 -> Polynomial c2 e2
forall coefficient exponent.
MonomialList coefficient exponent
-> Polynomial coefficient exponent
MkPolynomial (MonomialList c2 e2 -> Polynomial c2 e2)
-> (Polynomial c1 e1 -> MonomialList c2 e2)
-> Polynomial c1 e1
-> Polynomial c2 e2
forall b c a. (b -> c) -> (a -> b) -> a -> c
. MonomialList c1 e1 -> MonomialList c2 e2
transform (MonomialList c1 e1 -> MonomialList c2 e2)
-> (Polynomial c1 e1 -> MonomialList c1 e1)
-> Polynomial c1 e1
-> MonomialList c2 e2
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Polynomial c1 e1 -> MonomialList c1 e1
forall coefficient exponent.
Polynomial coefficient exponent
-> MonomialList coefficient exponent
getMonomialList
terms :: Polynomial c e -> Int
terms :: Polynomial c e -> Int
terms (MkPolynomial MonomialList c e
l) = MonomialList c e -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length MonomialList c e
l
getLeadingTerm :: Polynomial c e -> Data.Monomial.Monomial c e
getLeadingTerm :: Polynomial c e -> Monomial c e
getLeadingTerm (MkPolynomial []) = String -> Monomial c e
forall a. HasCallStack => String -> a
error String
"Factory.Data.Polynomial.getLeadingTerm:\tzero polynomial has no leading term."
getLeadingTerm (MkPolynomial (Monomial c e
m : [Monomial c e]
_)) = Monomial c e
m
pruneCoefficients :: (Eq c, Num c) => Polynomial c e -> Polynomial c e
pruneCoefficients :: Polynomial c e -> Polynomial c e
pruneCoefficients (MkPolynomial []) = Polynomial c e
forall c e. Polynomial c e
zero
pruneCoefficients Polynomial c e
p = (Monomial c e -> Bool) -> [Monomial c e] -> [Monomial c e]
forall a. (a -> Bool) -> [a] -> [a]
filter ((c -> c -> Bool
forall a. Eq a => a -> a -> Bool
/= c
0) (c -> Bool) -> (Monomial c e -> c) -> Monomial c e -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Monomial c e -> c
forall c e. Monomial c e -> c
Data.Monomial.getCoefficient) ([Monomial c e] -> [Monomial c e])
-> Polynomial c e -> Polynomial c e
forall c1 e1 c2 e2.
(MonomialList c1 e1 -> MonomialList c2 e2)
-> Polynomial c1 e1 -> Polynomial c2 e2
`lift` Polynomial c e
p
normalise :: (Eq c, Num c, Ord e) => Polynomial c e -> Polynomial c e
normalise :: Polynomial c e -> Polynomial c e
normalise = Polynomial c e -> Polynomial c e
forall c e. (Eq c, Num c) => Polynomial c e -> Polynomial c e
pruneCoefficients (Polynomial c e -> Polynomial c e)
-> (Polynomial c e -> Polynomial c e)
-> Polynomial c e
-> Polynomial c e
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (MonomialList c e -> MonomialList c e)
-> Polynomial c e -> Polynomial c e
forall c1 e1 c2 e2.
(MonomialList c1 e1 -> MonomialList c2 e2)
-> Polynomial c1 e1 -> Polynomial c2 e2
lift (
(MonomialList c e -> Monomial c e)
-> [MonomialList c e] -> MonomialList c e
forall a b. (a -> b) -> [a] -> [b]
map (
(Monomial c e -> c -> c) -> c -> MonomialList c e -> c
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (c -> c -> c
forall a. Num a => a -> a -> a
(+) (c -> c -> c) -> (Monomial c e -> c) -> Monomial c e -> c -> c
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Monomial c e -> c
forall c e. Monomial c e -> c
Data.Monomial.getCoefficient) c
0 (MonomialList c e -> c)
-> (MonomialList c e -> e) -> MonomialList c e -> Monomial c e
forall (a :: * -> * -> *) b c c'.
Arrow a =>
a b c -> a b c' -> a b (c, c')
&&& Monomial c e -> e
forall c e. Monomial c e -> e
Data.Monomial.getExponent (Monomial c e -> e)
-> (MonomialList c e -> Monomial c e) -> MonomialList c e -> e
forall b c a. (b -> c) -> (a -> b) -> a -> c
. MonomialList c e -> Monomial c e
forall a. [a] -> a
head
) ([MonomialList c e] -> MonomialList c e)
-> (MonomialList c e -> [MonomialList c e])
-> MonomialList c e
-> MonomialList c e
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Monomial c e -> Monomial c e -> Bool)
-> MonomialList c e -> [MonomialList c e]
forall a. (a -> a -> Bool) -> [a] -> [[a]]
Data.List.groupBy Monomial c e -> Monomial c e -> Bool
forall e c. Eq e => Monomial c e -> Monomial c e -> Bool
(=~) (MonomialList c e -> [MonomialList c e])
-> (MonomialList c e -> MonomialList c e)
-> MonomialList c e
-> [MonomialList c e]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Monomial c e -> Monomial c e -> Ordering)
-> MonomialList c e -> MonomialList c e
forall a. (a -> a -> Ordering) -> [a] -> [a]
Data.List.sortBy ((Monomial c e -> Monomial c e -> Ordering)
-> Monomial c e -> Monomial c e -> Ordering
forall a b c. (a -> b -> c) -> b -> a -> c
flip Monomial c e -> Monomial c e -> Ordering
forall e c. Ord e => Monomial c e -> Monomial c e -> Ordering
(<=>))
)
mkConstant :: (Eq c, Num c, Num e) => c -> Polynomial c e
mkConstant :: c -> Polynomial c e
mkConstant c
0 = Polynomial c e
forall c e. Polynomial c e
zero
mkConstant c
c = MonomialList c e -> Polynomial c e
forall coefficient exponent.
MonomialList coefficient exponent
-> Polynomial coefficient exponent
MkPolynomial [(c
c, e
0)]
mkLinear :: (Eq c, Num c, Num e)
=> c
-> c
-> Polynomial c e
mkLinear :: c -> c -> Polynomial c e
mkLinear c
m c
c = Polynomial c e -> Polynomial c e
forall c e. (Eq c, Num c) => Polynomial c e -> Polynomial c e
pruneCoefficients (Polynomial c e -> Polynomial c e)
-> Polynomial c e -> Polynomial c e
forall a b. (a -> b) -> a -> b
$ MonomialList c e -> Polynomial c e
forall coefficient exponent.
MonomialList coefficient exponent
-> Polynomial coefficient exponent
MkPolynomial [(c
m, e
1), (c
c, e
0)]
mkPolynomial :: (Eq c, Num c, Ord e) => MonomialList c e -> Polynomial c e
mkPolynomial :: MonomialList c e -> Polynomial c e
mkPolynomial [] = Polynomial c e
forall c e. Polynomial c e
zero
mkPolynomial MonomialList c e
l = Polynomial c e -> Polynomial c e
forall c e.
(Eq c, Num c, Ord e) =>
Polynomial c e -> Polynomial c e
normalise (Polynomial c e -> Polynomial c e)
-> Polynomial c e -> Polynomial c e
forall a b. (a -> b) -> a -> b
$ MonomialList c e -> Polynomial c e
forall coefficient exponent.
MonomialList coefficient exponent
-> Polynomial coefficient exponent
MkPolynomial MonomialList c e
l
zero :: Polynomial c e
zero :: Polynomial c e
zero = MonomialList c e -> Polynomial c e
forall coefficient exponent.
MonomialList coefficient exponent
-> Polynomial coefficient exponent
MkPolynomial []
one :: (Eq c, Num c, Num e) => Polynomial c e
one :: Polynomial c e
one = c -> Polynomial c e
forall c e. (Eq c, Num c, Num e) => c -> Polynomial c e
mkConstant c
1
inOrder :: (e -> e -> Bool) -> Polynomial c e -> Bool
inOrder :: (e -> e -> Bool) -> Polynomial c e -> Bool
inOrder e -> e -> Bool
comparator Polynomial c e
p
| ((Polynomial c e -> Bool) -> Bool)
-> [Polynomial c e -> Bool] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
any ((Polynomial c e -> Bool) -> Polynomial c e -> Bool
forall a b. (a -> b) -> a -> b
$ Polynomial c e
p) [Polynomial c e -> Bool
forall c e. Polynomial c e -> Bool
isZero, Polynomial c e -> Bool
forall c e. Polynomial c e -> Bool
isMonomial] = Bool
True
| Bool
otherwise = [Bool] -> Bool
forall (t :: * -> *). Foldable t => t Bool -> Bool
and ([Bool] -> Bool)
-> ([Monomial c e] -> [Bool]) -> [Monomial c e] -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ([e] -> [e] -> [Bool]) -> ([e], [e]) -> [Bool]
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry ((e -> e -> Bool) -> [e] -> [e] -> [Bool]
forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
zipWith e -> e -> Bool
comparator) (([e], [e]) -> [Bool])
-> ([Monomial c e] -> ([e], [e])) -> [Monomial c e] -> [Bool]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ([e] -> [e]
forall a. [a] -> [a]
init ([e] -> [e]) -> ([e] -> [e]) -> [e] -> ([e], [e])
forall (a :: * -> * -> *) b c c'.
Arrow a =>
a b c -> a b c' -> a b (c, c')
&&& [e] -> [e]
forall a. [a] -> [a]
tail) ([e] -> ([e], [e]))
-> ([Monomial c e] -> [e]) -> [Monomial c e] -> ([e], [e])
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Monomial c e -> e) -> [Monomial c e] -> [e]
forall a b. (a -> b) -> [a] -> [b]
map Monomial c e -> e
forall c e. Monomial c e -> e
Data.Monomial.getExponent ([Monomial c e] -> Bool) -> [Monomial c e] -> Bool
forall a b. (a -> b) -> a -> b
$ Polynomial c e -> [Monomial c e]
forall coefficient exponent.
Polynomial coefficient exponent
-> MonomialList coefficient exponent
getMonomialList Polynomial c e
p
inAscendingOrder :: Ord e => Polynomial c e -> Bool
inAscendingOrder :: Polynomial c e -> Bool
inAscendingOrder = (e -> e -> Bool) -> Polynomial c e -> Bool
forall e c. (e -> e -> Bool) -> Polynomial c e -> Bool
inOrder e -> e -> Bool
forall a. Ord a => a -> a -> Bool
(<=)
inDescendingOrder :: Ord e => Polynomial c e -> Bool
inDescendingOrder :: Polynomial c e -> Bool
inDescendingOrder = (e -> e -> Bool) -> Polynomial c e -> Bool
forall e c. (e -> e -> Bool) -> Polynomial c e -> Bool
inOrder e -> e -> Bool
forall a. Ord a => a -> a -> Bool
(>=)
isReduced :: (Eq c, Num c) => Polynomial c e -> Bool
isReduced :: Polynomial c e -> Bool
isReduced = (Monomial c e -> Bool) -> [Monomial c e] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all ((c -> c -> Bool
forall a. Eq a => a -> a -> Bool
/= c
0) (c -> Bool) -> (Monomial c e -> c) -> Monomial c e -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Monomial c e -> c
forall c e. Monomial c e -> c
Data.Monomial.getCoefficient) ([Monomial c e] -> Bool)
-> (Polynomial c e -> [Monomial c e]) -> Polynomial c e -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Polynomial c e -> [Monomial c e]
forall coefficient exponent.
Polynomial coefficient exponent
-> MonomialList coefficient exponent
getMonomialList
isNormalised :: (Eq c, Num c, Ord e) => Polynomial c e -> Bool
isNormalised :: Polynomial c e -> Bool
isNormalised Polynomial c e
polynomial = ((Polynomial c e -> Bool) -> Bool)
-> [Polynomial c e -> Bool] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all ((Polynomial c e -> Bool) -> Polynomial c e -> Bool
forall a b. (a -> b) -> a -> b
$ Polynomial c e
polynomial) [Polynomial c e -> Bool
forall c e. (Eq c, Num c) => Polynomial c e -> Bool
isReduced, Polynomial c e -> Bool
forall e c. Ord e => Polynomial c e -> Bool
inDescendingOrder]
isMonic :: (Eq c, Num c) => Polynomial c e -> Bool
isMonic :: Polynomial c e -> Bool
isMonic (MkPolynomial []) = Bool
False
isMonic Polynomial c e
p = (c -> c -> Bool
forall a. Eq a => a -> a -> Bool
== c
1) (c -> Bool) -> (Monomial c e -> c) -> Monomial c e -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Monomial c e -> c
forall c e. Monomial c e -> c
Data.Monomial.getCoefficient (Monomial c e -> Bool) -> Monomial c e -> Bool
forall a b. (a -> b) -> a -> b
$ Polynomial c e -> Monomial c e
forall c e. Polynomial c e -> Monomial c e
getLeadingTerm Polynomial c e
p
isZero :: Polynomial c e -> Bool
isZero :: Polynomial c e -> Bool
isZero (MkPolynomial []) = Bool
True
isZero Polynomial c e
_ = Bool
False
isMonomial :: Polynomial c e -> Bool
isMonomial :: Polynomial c e -> Bool
isMonomial (MkPolynomial []) = Bool
True
isMonomial Polynomial c e
_ = Bool
False
isPolynomial :: Integral e => Polynomial c e -> Bool
isPolynomial :: Polynomial c e -> Bool
isPolynomial = (Monomial c e -> Bool) -> [Monomial c e] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all Monomial c e -> Bool
forall e c. Integral e => Monomial c e -> Bool
Data.Monomial.isMonomial ([Monomial c e] -> Bool)
-> (Polynomial c e -> [Monomial c e]) -> Polynomial c e -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Polynomial c e -> [Monomial c e]
forall coefficient exponent.
Polynomial coefficient exponent
-> MonomialList coefficient exponent
getMonomialList
areCongruentModulo :: (Integral c, Num e, Ord e)
=> Polynomial c e
-> Polynomial c e
-> c
-> Bool
areCongruentModulo :: Polynomial c e -> Polynomial c e -> c -> Bool
areCongruentModulo Polynomial c e
_ Polynomial c e
_ c
0 = String -> Bool
forall a. HasCallStack => String -> a
error String
"Factory.Data.Polynomial.areCongruentModulo:\tzero modulus."
areCongruentModulo Polynomial c e
_ Polynomial c e
_ c
1 = Bool
True
areCongruentModulo Polynomial c e
l Polynomial c e
r c
modulus
| Polynomial c e
l Polynomial c e -> Polynomial c e -> Bool
forall a. Eq a => a -> a -> Bool
== Polynomial c e
r = Bool
True
| Bool
otherwise = (Monomial c e -> Bool) -> [Monomial c e] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all ((c -> c -> Bool
forall a. Eq a => a -> a -> Bool
== c
0) (c -> Bool) -> (Monomial c e -> c) -> Monomial c e -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (c -> c -> c
forall a. Integral a => a -> a -> a
`mod` c
modulus) (c -> c) -> (Monomial c e -> c) -> Monomial c e -> c
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Monomial c e -> c
forall c e. Monomial c e -> c
Data.Monomial.getCoefficient) ([Monomial c e] -> Bool)
-> (Polynomial c e -> [Monomial c e]) -> Polynomial c e -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Polynomial c e -> [Monomial c e]
forall coefficient exponent.
Polynomial coefficient exponent
-> MonomialList coefficient exponent
getMonomialList (Polynomial c e -> Bool) -> Polynomial c e -> Bool
forall a b. (a -> b) -> a -> b
$ Polynomial c e
l Polynomial c e -> Polynomial c e -> Polynomial c e
forall r. Ring r => r -> r -> r
=-= Polynomial c e
r
getDegree :: Num e => Polynomial c e -> e
getDegree :: Polynomial c e -> e
getDegree (MkPolynomial []) = -e
1
getDegree Polynomial c e
p = Monomial c e -> e
forall c e. Monomial c e -> e
Data.Monomial.getExponent (Monomial c e -> e) -> Monomial c e -> e
forall a b. (a -> b) -> a -> b
$ Polynomial c e -> Monomial c e
forall c e. Polynomial c e -> Monomial c e
getLeadingTerm Polynomial c e
p
(*=) :: (Eq c, Num c, Num e) => Polynomial c e -> Data.Monomial.Monomial c e -> Polynomial c e
Polynomial c e
polynomial *= :: Polynomial c e -> Monomial c e -> Polynomial c e
*= Monomial c e
monomial
| Monomial c e -> c
forall c e. Monomial c e -> c
Data.Monomial.getCoefficient Monomial c e
monomial c -> c -> Bool
forall a. Eq a => a -> a -> Bool
== c
1 = (Monomial c e -> Monomial c e) -> [Monomial c e] -> [Monomial c e]
forall a b. (a -> b) -> [a] -> [b]
map (Monomial c e -> e -> Monomial c e
forall e c. Num e => Monomial c e -> e -> Monomial c e
`Data.Monomial.shiftExponent` Monomial c e -> e
forall c e. Monomial c e -> e
Data.Monomial.getExponent Monomial c e
monomial) ([Monomial c e] -> [Monomial c e])
-> Polynomial c e -> Polynomial c e
forall c1 e1 c2 e2.
(MonomialList c1 e1 -> MonomialList c2 e2)
-> Polynomial c1 e1 -> Polynomial c2 e2
`lift` Polynomial c e
polynomial
| Bool
otherwise = (Monomial c e -> Monomial c e) -> [Monomial c e] -> [Monomial c e]
forall a b. (a -> b) -> [a] -> [b]
map (Monomial c e
monomial Monomial c e -> Monomial c e -> Monomial c e
forall c e.
(Num c, Num e) =>
Monomial c e -> Monomial c e -> Monomial c e
<*>) ([Monomial c e] -> [Monomial c e])
-> Polynomial c e -> Polynomial c e
forall c1 e1 c2 e2.
(MonomialList c1 e1 -> MonomialList c2 e2)
-> Polynomial c1 e1 -> Polynomial c2 e2
`lift` Polynomial c e
polynomial
raiseModulo :: (Integral c, Integral power, Num e, Ord e, Show power)
=> Polynomial c e
-> power
-> c
-> Polynomial c e
raiseModulo :: Polynomial c e -> power -> c -> Polynomial c e
raiseModulo Polynomial c e
_ power
_ c
0 = String -> Polynomial c e
forall a. HasCallStack => String -> a
error String
"Factory.Data.Polynomial.raiseModulo:\tzero modulus."
raiseModulo Polynomial c e
_ power
_ c
1 = Polynomial c e
forall c e. Polynomial c e
zero
raiseModulo Polynomial c e
_ power
0 c
modulus = c -> Polynomial c e
forall c e. (Eq c, Num c, Num e) => c -> Polynomial c e
mkConstant (c -> Polynomial c e) -> c -> Polynomial c e
forall a b. (a -> b) -> a -> b
$ c
1 c -> c -> c
forall a. Integral a => a -> a -> a
`mod` c
modulus
raiseModulo Polynomial c e
polynomial power
power c
modulus
| power
power power -> power -> Bool
forall a. Ord a => a -> a -> Bool
< power
0 = String -> Polynomial c e
forall a. HasCallStack => String -> a
error (String -> Polynomial c e) -> String -> Polynomial c e
forall a b. (a -> b) -> a -> b
$ String
"Factory.Data.Polynomial.raiseModulo:\tthe result isn't guaranteed to be a polynomial, for power=" String -> ShowS
forall a. [a] -> [a] -> [a]
++ power -> String
forall a. Show a => a -> String
show power
power
| Polynomial c e
first Polynomial c e -> [Polynomial c e] -> Bool
forall (t :: * -> *) a. (Foldable t, Eq a) => a -> t a -> Bool
`elem` [Polynomial c e
forall c e. Polynomial c e
zero, Polynomial c e
forall c e. (Eq c, Num c, Num e) => Polynomial c e
one] = Polynomial c e
first
| Bool
otherwise = power -> Polynomial c e
forall t. Integral t => t -> Polynomial c e
slave power
power
where
first :: Polynomial c e
first = Polynomial c e
polynomial Polynomial c e -> c -> Polynomial c e
forall c e. Integral c => Polynomial c e -> c -> Polynomial c e
`mod'` c
modulus
slave :: t -> Polynomial c e
slave t
1 = Polynomial c e
first
slave t
n = (Polynomial c e -> c -> Polynomial c e
forall c e. Integral c => Polynomial c e -> c -> Polynomial c e
`mod'` c
modulus) (Polynomial c e -> Polynomial c e)
-> (Polynomial c e -> Polynomial c e)
-> Polynomial c e
-> Polynomial c e
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (if t
r t -> t -> Bool
forall a. Eq a => a -> a -> Bool
== t
0 then Polynomial c e -> Polynomial c e
forall a. a -> a
id else (Polynomial c e
polynomial Polynomial c e -> Polynomial c e -> Polynomial c e
forall r. Ring r => r -> r -> r
=*=)) (Polynomial c e -> Polynomial c e)
-> (Polynomial c e -> Polynomial c e)
-> Polynomial c e
-> Polynomial c e
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Polynomial c e -> Polynomial c e
forall r. Ring r => r -> r
Data.Ring.square (Polynomial c e -> Polynomial c e)
-> Polynomial c e -> Polynomial c e
forall a b. (a -> b) -> a -> b
$ t -> Polynomial c e
slave t
q where
(t
q, t
r) = t
n t -> t -> (t, t)
forall a. Integral a => a -> a -> (a, a)
`quotRem` t
2
mod' :: Integral c
=> Polynomial c e
-> c
-> Polynomial c e
mod' :: Polynomial c e -> c -> Polynomial c e
mod' Polynomial c e
p c
modulus = Polynomial c e -> Polynomial c e
forall c e. (Eq c, Num c) => Polynomial c e -> Polynomial c e
pruneCoefficients (Polynomial c e -> Polynomial c e)
-> Polynomial c e -> Polynomial c e
forall a b. (a -> b) -> a -> b
$ (Monomial c e -> Monomial c e) -> [Monomial c e] -> [Monomial c e]
forall a b. (a -> b) -> [a] -> [b]
map (Monomial c e -> c -> Monomial c e
forall c e. Integral c => Monomial c e -> c -> Monomial c e
`Data.Monomial.mod'` c
modulus) ([Monomial c e] -> [Monomial c e])
-> Polynomial c e -> Polynomial c e
forall c1 e1 c2 e2.
(MonomialList c1 e1 -> MonomialList c2 e2)
-> Polynomial c1 e1 -> Polynomial c2 e2
`lift` Polynomial c e
p
evaluate :: (Num n, Integral e, Show e)
=> n
-> Polynomial n e
-> n
evaluate :: n -> Polynomial n e -> n
evaluate n
x = (Monomial n e -> n -> n) -> n -> [Monomial n e] -> n
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (n -> n -> n
forall a. Num a => a -> a -> a
(+) (n -> n -> n) -> (Monomial n e -> n) -> Monomial n e -> n -> n
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Monomial n e -> n
forall i. (Show i, Integral i) => Monomial n i -> n
raise) n
0 ([Monomial n e] -> n)
-> (Polynomial n e -> [Monomial n e]) -> Polynomial n e -> n
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Polynomial n e -> [Monomial n e]
forall coefficient exponent.
Polynomial coefficient exponent
-> MonomialList coefficient exponent
getMonomialList where
powers :: [n]
powers = (n -> n) -> n -> [n]
forall a. (a -> a) -> a -> [a]
iterate (n -> n -> n
forall a. Num a => a -> a -> a
* n
x) n
1
raise :: Monomial n i -> n
raise Monomial n i
monomial
| i
exponent' i -> i -> Bool
forall a. Ord a => a -> a -> Bool
< i
0 = String -> n
forall a. HasCallStack => String -> a
error (String -> n) -> String -> n
forall a b. (a -> b) -> a -> b
$ String
"Factory.Data.Polynomial.evaluate.raise:\tnegative exponent; " String -> ShowS
forall a. [a] -> [a] -> [a]
++ i -> String
forall a. Show a => a -> String
show i
exponent'
| Bool
otherwise = Monomial n i -> n
forall c e. Monomial c e -> c
Data.Monomial.getCoefficient Monomial n i
monomial n -> n -> n
forall a. Num a => a -> a -> a
* [n] -> i -> n
forall i a. Integral i => [a] -> i -> a
Data.List.genericIndex [n]
powers i
exponent'
where
exponent' :: i
exponent' = Monomial n i -> i
forall c e. Monomial c e -> e
Data.Monomial.getExponent Monomial n i
monomial
realCoefficientsToFrac :: (Real r, Fractional f) => Polynomial r e -> Polynomial f e
realCoefficientsToFrac :: Polynomial r e -> Polynomial f e
realCoefficientsToFrac = (MonomialList r e -> MonomialList f e)
-> Polynomial r e -> Polynomial f e
forall c1 e1 c2 e2.
(MonomialList c1 e1 -> MonomialList c2 e2)
-> Polynomial c1 e1 -> Polynomial c2 e2
lift (Monomial r e -> Monomial f e
forall r f e.
(Real r, Fractional f) =>
Monomial r e -> Monomial f e
Data.Monomial.realCoefficientToFrac (Monomial r e -> Monomial f e)
-> MonomialList r e -> MonomialList f e
forall a b. (a -> b) -> [a] -> [b]
`map`)