factory-0.0.0.2: Rational arithmetic in an irrational world.

Factory.Data.Polynomial

Description

`AUTHOR`
Dr. Alistair Ward
`DESCRIPTION`

Synopsis

# Types

## Data-types,

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 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 http://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.

Instances

 (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 `Ring`, over the field composed from all possible coefficients; http://en.wikipedia.org/wiki/Polynomial_ring. (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

Arguments

 :: (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.

getLeadingTerm :: Polynomial c e -> Monomial c eSource

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

Arguments

 :: 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`.

Arguments

 :: (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 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.

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

## Constructors

mkConstant :: (Num c, Num e) => c -> Polynomial c eSource

Constructs an arbitrary zeroeth-degree polynomial, ie. independent of the indeterminate.

Arguments

 :: (Num c, Num e) => c Gradient. -> c Constant. -> Polynomial c e

Constructs an arbitrary first-degree 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

## Predicates

Arguments

 :: (Integral c, Num e, Ord e) => Polynomial c e LHS. -> Polynomial c e RHS. -> c Modulus. -> Bool

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

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.