{-# LANGUAGE CPP #-}
{-
	Copyright (C) 2011-2015 Dr. Alistair Ward

	This program is free software: you can redistribute it and/or modify
	it under the terms of the GNU General Public License as published by
	the Free Software Foundation, either version 3 of the License, or
	(at your option) any later version.

	This program is distributed in the hope that it will be useful,
	but WITHOUT ANY WARRANTY; without even the implied warranty of
	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
	GNU General Public License for more details.

	You should have received a copy of the GNU General Public License
	along with this program.  If not, see <https://www.gnu.org/licenses/>.
-}
{- |
 [@AUTHOR@]	Dr. Alistair Ward

 [@DESCRIPTION@]

	* Describes a <https://en.wikipedia.org/wiki/Univariate> polynomial and operations on it.

	* <https://en.wikipedia.org/wiki/Polynomial>.

	* <https://mathworld.wolfram.com/Polynomial.html>.
-}

module Factory.Data.Polynomial(
-- * Types
-- ** Type-synonyms
--	MonomialList,
-- ** Data-types
	Polynomial,
-- * Constants
	zero,
	one,
-- * Functions
	evaluate,
	getDegree,
	getLeadingTerm,
	lift,
	mod',
	normalise,
--	pruneCoefficients,
	raiseModulo,
	realCoefficientsToFrac,
	terms,
-- ** Constructors
	mkConstant,
	mkLinear,
	mkPolynomial,
-- ** Operators
	(*=),
-- ** Predicates
	areCongruentModulo,
	inAscendingOrder,
	inDescendingOrder,
--	inOrder,
	isMonic,
	isMonomial,
	isNormalised,
	isPolynomial,
--	isReduced,
	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 ((<*>))	-- The "Prelude" from 'base-4.8' exports this symbol.
#endif

infixl 7 *=	-- Same as (*).

-- | The guts of a 'Polynomial'.
type MonomialList coefficient exponent	= [Data.Monomial.Monomial coefficient exponent]

{- |
	* The type of an arbitrary /univariate/ polynomial;
	actually it's more general, since it permits negative powers (<https://en.wikipedia.org/wiki/Laurent_polynomial>s).
	It can't describe /multivariate/ polynomials, which would require a list of /exponents/.
	Rather than requiring the /exponent/ to implement the /type-class/ 'Integral', this is implemented at the function-level, as required.

	* The structure permits gaps between /exponents/,
	in which /coefficients/ are inferred to be zero, thus enabling efficient representation of sparse polynomials.

	* CAVEAT: the 'MonomialList' is required to;
	be ordered by /descending/ exponent (ie. reverse <https://en.wikipedia.org/wiki/Monomial_order>);
	have had zero coefficients removed;
	and to have had /like/ terms merged;
	so the raw data-constructor isn't exported.
-}
newtype {- Integral exponent => -} Polynomial coefficient exponent	= MkPolynomial {
	Polynomial coefficient exponent
-> MonomialList coefficient exponent
getMonomialList	:: MonomialList coefficient exponent	-- ^ Accessor.
} 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)

-- | Makes /Polynomial/ a 'Data.Ring.Ring', over the /field/ composed from all possible /coefficients/; <https://en.wikipedia.org/wiki/Polynomial_ring>.
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
--		| polynomialL == one			= polynomialR	-- Counterproductive.
--		| polynomialR == one			= polynomialL	-- Counterproductive.
		| 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) {-TODO-} Int
10 {-empirical-} ([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

{-
	Override the default implementation,
	in order to take advantage of the symmetry under reflection about the main diagonal,
	in the square matrix of products formed from the multiplication of each term by each term.
	Eg:
		(ax^3 + bx^2 + cx + d)^2 = [
			(a^2x^6 + abx^5 + acx^4 + adx^3) +
			(bax^5 + b^2x^4 + bcx^3 + bdx^2) +
			(cax^4 + cbx^3 + c^2x^2 + cdx) +
			(dax^3 + dbx^2 + dcx + d^2)
		]

		= (a^2x^6 + b^2x^4 + c^2x^2 + d^2) + 2 * [ax^3 * (bx^2 + cx + d) + bx^2 * (cx + d) + cx * (d)]
-}
	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) {-TODO-} Int
10 {-empirical-} ([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 {-remove terminal null-} ([[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

-- | Defines the ability to divide /polynomials/.
instance (
	Eq		c,
	Fractional	c,
	Num		e,
	Ord		e
 ) => Data.QuotientRing.QuotientRing (Polynomial c e)	where
{-
	Uses /Euclidian division/.
	<https://en.wikipedia.org/wiki/Polynomial_long_division>.
	<https://demonstrations.wolfram.com/PolynomialLongDivision/>.
-}
	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 :: (Fractional c, Num e, Ord e) => Polynomial c e -> (Polynomial c e, Polynomial c e)
		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)	-- Exactly divides.
		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)	-- Indivisible remainder.
			| 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 :: (Fractional c, Num e) => Data.Monomial.Monomial c e
				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

{- |
	* Transforms the data behind the constructor.

	* CAVEAT: similar to 'Data.Functor.fmap', but 'Polynomial' isn't an instance of 'Data.Functor.Functor' since we may want to operate on both /type-parameters/.

	* CAVEAT: the caller is required to re-'normalise' the resulting polynomial depending on the nature of the transformation of the data.
-}
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

-- | Returns the number of non-zero terms in the polynomial.
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

-- | Return the highest-degree monomial.
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

-- | Removes terms with a /coefficient/ of zero.
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

-- | Sorts into /descending order/ of exponents, groups /like/ exponents, and calls 'pruneCoefficients'.
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
(<=>))
 )

-- | Constructs an arbitrary /zeroeth-degree polynomial/, ie. independent of the /indeterminate/.
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)]

-- | Constructs an arbitrary /first-degree polynomial/.
mkLinear :: (Eq c, Num c, Num e)
	=> c	-- ^ Gradient.
	-> c	-- ^ Constant.
	-> 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)]

-- | Smart constructor. Constructs an arbitrary /polynomial/.
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

-- | Constructs a /polynomial/ with zero terms.
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 []

-- | Constructs a constant /monomial/, independent of the /indeterminate/.
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

-- | True if all /exponents/ are in the order defined by the specified comparator.
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

-- | True if the /exponents/ of successive terms are in /ascending/ order.
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
(<=)

-- | True if the /exponents/ of successive terms are in /descending/ order.
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
(>=)

-- | True if no term has a /coefficient/ of zero.
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

-- | True if no term has a /coefficient/ of zero and the /exponents/ of successive terms are in /descending/ order.
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]

{- |
	* 'True' if the /leading coefficient/ is one.

	* <https://en.wikipedia.org/wiki/Monic_polynomial#Classifications>.
-}
isMonic :: (Eq c, Num c) => Polynomial c e -> Bool
isMonic :: Polynomial c e -> Bool
isMonic (MkPolynomial [])	= Bool
False	-- All coefficients are zero, and have therefore been removed.
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

-- | True if there are zero terms.
isZero :: Polynomial c e -> Bool
isZero :: Polynomial c e -> Bool
isZero (MkPolynomial [])	= Bool
True
isZero Polynomial c e
_			= Bool
False

-- | True if there's exactly one term.
isMonomial :: Polynomial c e -> Bool
isMonomial :: Polynomial c e -> Bool
isMonomial (MkPolynomial [])	= Bool
True
isMonomial Polynomial c e
_			= Bool
False

-- | True if all /exponents/ are /positive/ integers as required.
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

{- |
	* 'True' if the two specified /polynomials/ are /congruent/ in /modulo/-arithmetic.

	* <https://planetmath.org/encyclopedia/PolynomialCongruence.html>.
-}
areCongruentModulo :: (Integral c, Num e, Ord e)
	=> Polynomial c e	-- ^ LHS.
	-> Polynomial c e	-- ^ RHS.
	-> c			-- ^ Modulus.
	-> 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

{- |
	* Return the /degree/ (AKA /order/) of the /polynomial/.

	* <https://en.wikipedia.org/wiki/Degree_of_a_polynomial>.

	* <https://mathworld.wolfram.com/PolynomialDegree.html>.
-}
getDegree :: Num e => Polynomial c e -> e
getDegree :: Polynomial c e -> e
getDegree (MkPolynomial [])	= -e
1	-- CAVEAT: debatable, but makes some operations more robust and consistent.
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

{- |
	* Scale-up the specified /polynomial/ by a constant /monomial/ factor.

	* <https://en.wikipedia.org/wiki/Scalar_multiplication>.
-}
(*=) :: (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

{- |
	* Raise a /polynomial/ to the specified positive integral power, but using /modulo/-arithmetic.

	* Whilst one could naively implement this as @(x Data.Ring.=^ n) `mod` m@, this will result in arithmetic operatons on unnecessarily big integers.
-}
raiseModulo :: (Integral c, Integral power, Num e, Ord e, Show power)
	=> Polynomial c e	-- ^ The base.
	-> power		-- ^ The exponent to which the base should be raised.
	-> c			-- ^ The modulus.
	-> Polynomial c e	-- ^ The result.
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	-- Eg 'raiseModulo (mkPolynomial [(3,1)]) 100 3' or 'raiseModulo (mkPolynomial [(3,1),(1,0)]) 100 3'.
	| Bool
otherwise			= power -> Polynomial c e
forall t. Integral t => t -> Polynomial c e
slave power
power
	where
--		first :: Integral c => Polynomial c e
		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 :: (Integral c, Integral power, Num e, Ord e) => power -> Polynomial c e
		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 {-even-} 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 {-recurse-}	where
			(t
q, t
r)	= t
n t -> t -> (t, t)
forall a. Integral a => a -> a -> (a, a)
`quotRem` t
2

-- | Reduces all the coefficients using /modular/ arithmetic.
mod' :: Integral c
	=> Polynomial c e
	-> c	-- ^ Modulus.
	-> 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 the /polynomial/ at a specific /indeterminate/.

	* CAVEAT: requires positive exponents; but it wouldn't really be a /polynomial/ otherwise.

	* If the /polynomial/ is very sparse, this may be inefficient,
	since it /memoizes/ the complete sequence of powers up to the polynomial's /degree/.
-}
evaluate :: (Num n, Integral e, Show e)
	=> n	-- ^ The /indeterminate/.
	-> Polynomial n e
	-> n	-- ^ The Result.
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

-- | Convert the type of the /coefficient/s.
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`)