AUTHOR
 Dr. Alistair Ward
DESCRIPTION
 Describes a http://en.wikipedia.org/wiki/Univariate polynomial and operations on it.
 http://en.wikipedia.org/wiki/Polynomial.
 http://mathworld.wolfram.com/Polynomial.html.
 data Polynomial coefficient exponent
 zero :: Polynomial c e
 one :: (Num c, Num e) => Polynomial c e
 evaluate :: (Num n, Integral e) => n > Polynomial n e > n
 getDegree :: Num e => Polynomial c e > e
 getLeadingTerm :: Polynomial c e > Monomial c e
 lift :: (MonomialList c1 e1 > MonomialList c2 e2) > Polynomial c1 e1 > Polynomial c2 e2
 mod' :: Integral c => Polynomial c e > c > Polynomial c e
 normalise :: (Num c, Ord e) => Polynomial c e > Polynomial c e
 raiseModulo :: (Integral c, Integral power, Num e, Ord e) => Polynomial c e > power > c > Polynomial c e
 realCoefficientsToFrac :: (Real r, Fractional f) => Polynomial r e > Polynomial f e
 terms :: Polynomial c e > Int
 mkConstant :: (Num c, Num e) => c > Polynomial c e
 mkLinear :: (Num c, Num e) => c > c > Polynomial c e
 mkPolynomial :: (Num c, Ord e) => MonomialList c e > Polynomial c e
 (*=) :: (Num c, Num e) => Polynomial c e > Monomial c e > Polynomial c e
 areCongruentModulo :: (Integral c, Num e, Ord e) => Polynomial c e > Polynomial c e > c > Bool
 inAscendingOrder :: Ord e => Polynomial c e > Bool
 inDescendingOrder :: Ord e => Polynomial c e > Bool
 isMonic :: Num c => Polynomial c e > Bool
 isMonomial :: Polynomial c e > Bool
 isNormalised :: (Num c, Ord e) => Polynomial c e > Bool
 isPolynomial :: Integral e => Polynomial c e > Bool
 isZero :: Polynomial c e > Bool
Types
Typesynonyms
Datatypes,
data Polynomial coefficient exponent Source
 The type of an arbitrary univariate polynomial;
actually it's more general, since it permits negative powers (http://en.wikipedia.org/wiki/Laurent_polynomials).
It can't describe multivariate polynomials, which would require a list of exponents.
Rather than requiring the exponent to implement the typeclass
Integral
, this is implemented at the functionlevel, 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 http://en.wikipedia.org/wiki/Monomial_order); have had zero coefficients removed; and to have had like terms merged; so the raw dataconstructor isn't exported.
(Eq coefficient, Eq exponent) => Eq (Polynomial coefficient exponent)  
(Show coefficient, Show exponent) => Show (Polynomial coefficient exponent)  
(Num c, Num e, Ord e) => Ring (Polynomial c e)  Makes Polynomial a 
(Fractional c, Num e, Ord e) => QuotientRing (Polynomial c e)  Defines the ability to divide polynomials. 
Constants
zero :: Polynomial c eSource
Constructs a polynomial with zero terms.
one :: (Num c, Num e) => Polynomial c eSource
Constructs a constant monomial, independent of the indeterminate.
Functions
:: (Num n, Integral e)  
=> n  The indeterminate. 
> Polynomial n e  
> n  The Result. 
 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.
getDegree :: Num e => Polynomial c e > eSource
 Return the degree (AKA order) of the polynomial.
 http://en.wikipedia.org/wiki/Degree_of_a_polynomial.
 http://mathworld.wolfram.com/PolynomialDegree.html.
getLeadingTerm :: Polynomial c e > Monomial c eSource
Return the highestdegree monomial.
lift :: (MonomialList c1 e1 > MonomialList c2 e2) > Polynomial c1 e1 > Polynomial c2 e2Source
 Transforms the data behind the constructor.
 CAVEAT: similar to
Data.Functor.fmap
, butPolynomial
isn't an instance ofData.Functor.Functor
since we may want to operate on both typeparameters.  CAVEAT: the caller is required to re
normalise
the resulting polynomial depending on the nature of the transformation of the data.
:: Integral c  
=> Polynomial c e  
> c  Modulus. 
> Polynomial c e 
Reduces all the coefficients using modular arithmetic.
normalise :: (Num c, Ord e) => Polynomial c e > Polynomial c eSource
Sorts into descending order of exponents, groups like exponents, and calls pruneCoefficients
.
:: (Integral c, Integral power, Num e, Ord e)  
=> Polynomial c e  The base. 
> power  The exponent to which the base should be raised. 
> c  The modulus. 
> Polynomial c e  The result. 
 Raise a polynomial to the specified positive integral power, but using moduloarithmetic.
 Whilst one could naively implement this as
(x Data.Ring.=^ n)
, this will result in arithmetic operatons on unnecessarily big integers.mod
m
realCoefficientsToFrac :: (Real r, Fractional f) => Polynomial r e > Polynomial f eSource
Convert the type of the coefficients.
terms :: Polynomial c e > IntSource
Returns the number of nonzero terms in the polynomial.
Constructors
mkConstant :: (Num c, Num e) => c > Polynomial c eSource
Constructs an arbitrary zeroethdegree polynomial, ie. independent of the indeterminate.
:: (Num c, Num e)  
=> c  Gradient. 
> c  Constant. 
> Polynomial c e 
Constructs an arbitrary firstdegree polynomial.
mkPolynomial :: (Num c, Ord e) => MonomialList c e > Polynomial c eSource
Constructs an arbitrary polynomial.
Operators
(*=) :: (Num c, Num e) => Polynomial c e > Monomial c e > Polynomial c eSource
 Scaleup the specified polynomial by a constant monomial factor.
 http://en.wikipedia.org/wiki/Scalar_multiplication.
Predicates
:: (Integral c, Num e, Ord e)  
=> Polynomial c e  LHS. 
> Polynomial c e  RHS. 
> c  Modulus. 
> Bool 

True
if the two specified polynomials are congruent in moduloarithmetic.  http://planetmath.org/encyclopedia/PolynomialCongruence.html.
inAscendingOrder :: Ord e => Polynomial c e > BoolSource
True
if the exponents of successive terms are in ascending order.
inDescendingOrder :: Ord e => Polynomial c e > BoolSource
True
if the exponents of successive terms are in descending order.
isMonic :: Num c => Polynomial c e > BoolSource

True
if the leading coefficient is one.  http://en.wikipedia.org/wiki/Monic_polynomial#Classifications.
isMonomial :: Polynomial c e > BoolSource
True
if there's exactly one term.
isNormalised :: (Num c, Ord e) => Polynomial c e > BoolSource
True
if no term has a coefficient of zero and the exponents of successive terms are in descending order.
isPolynomial :: Integral e => Polynomial c e > BoolSource
True
if all exponents are positive integers as required.
isZero :: Polynomial c e > BoolSource
True
if there are zero terms.