Safe Haskell | None |
---|---|

Language | Haskell2010 |

This module provides abstract classes for finitary polynomial types.

## Synopsis

- class (CoeffRing (Coefficient poly), Eq poly, DecidableZero poly, KnownNat (Arity poly), Module (Scalar (Coefficient poly)) poly, Ring poly, Commutative poly) => IsPolynomial poly where
- type Coefficient poly :: Type
- type Arity poly :: Nat

- class (IsMonomialOrder (Arity poly) (MOrder poly), IsPolynomial poly) => IsOrderedPolynomial poly where
- substCoeff :: IsPolynomial poly => Sized (Arity poly) (Coefficient poly) -> poly -> Coefficient poly
- liftMapCoeff :: IsPolynomial poly => (Ordinal (Arity poly) -> Coefficient poly) -> poly -> Coefficient poly
- class (DecidableZero r, Ring r, Commutative r, Eq r) => CoeffRing r
- oneNorm :: (IsPolynomial poly, Normed (Coefficient poly), Monoidal (Norm (Coefficient poly))) => poly -> Norm (Coefficient poly)
- maxNorm :: (IsPolynomial poly, Normed (Coefficient poly)) => poly -> Norm (Coefficient poly)
- monoize :: (Field (Coefficient poly), IsOrderedPolynomial poly) => poly -> poly
- sPolynomial :: (IsOrderedPolynomial poly, Field (Coefficient poly)) => poly -> poly -> poly
- pDivModPoly :: (k ~ Coefficient poly, Euclidean k, IsOrderedPolynomial poly) => poly -> poly -> (poly, poly)
- content :: (IsPolynomial poly, Euclidean (Coefficient poly)) => poly -> Coefficient poly
- pp :: (Euclidean (Coefficient poly), IsPolynomial poly) => poly -> poly
- injectVars :: ((Arity r <= Arity r') ~ True, IsPolynomial r, IsPolynomial r', Coefficient r ~ Coefficient r') => r -> r'
- vars :: forall poly. IsPolynomial poly => [poly]
- class Show r => PrettyCoeff r where
- data ShowSCoeff
- showsCoeffAsTerm :: ShowSCoeff -> ShowS
- showsCoeffWithOp :: ShowSCoeff -> ShowS
- showsPolynomialWith :: (IsPolynomial poly, PrettyCoeff (Coefficient poly)) => Sized (Arity poly) String -> Int -> poly -> ShowS
- showsPolynomialWith' :: IsPolynomial poly => Bool -> (Int -> Coefficient poly -> ShowSCoeff) -> Sized (Arity poly) String -> Int -> poly -> ShowS
- showPolynomialWith :: (IsPolynomial poly, PrettyCoeff (Coefficient poly)) => Sized (Arity poly) String -> Int -> poly -> String
- showPolynomialWith' :: IsPolynomial poly => Bool -> (Int -> Coefficient poly -> ShowSCoeff) -> Sized (Arity poly) String -> Int -> poly -> String
- divModPolynomial :: (IsOrderedPolynomial poly, Field (Coefficient poly)) => poly -> [poly] -> ([(poly, poly)], poly)
- divPolynomial :: (IsOrderedPolynomial poly, Field (Coefficient poly)) => poly -> [poly] -> [(poly, poly)]
- modPolynomial :: (IsOrderedPolynomial poly, Field (Coefficient poly)) => poly -> [poly] -> poly
- convertPolynomial :: (IsOrderedPolynomial poly, IsOrderedPolynomial poly', Coefficient poly ~ Coefficient poly', MOrder poly ~ MOrder poly', Arity poly ~ Arity poly') => poly -> poly'
- convertPolynomial' :: (IsOrderedPolynomial poly, IsOrderedPolynomial poly', Coefficient poly ~ Coefficient poly', Arity poly ~ Arity poly') => poly -> poly'
- mapPolynomial :: (IsOrderedPolynomial poly, IsOrderedPolynomial poly') => (Coefficient poly -> Coefficient poly') -> (Ordinal (Arity poly) -> Ordinal (Arity poly')) -> poly -> poly'
- isUnitDefault :: (DecidableUnits r, Coefficient poly ~ r, IsPolynomial poly) => poly -> Bool
- recipUnitDefault :: (DecidableUnits r, Coefficient poly ~ r, IsPolynomial poly) => poly -> Maybe poly
- isAssociateDefault :: (UnitNormalForm r, Coefficient poly ~ r, IsOrderedPolynomial poly) => poly -> poly -> Bool
- splitUnitDefault :: (UnitNormalForm r, Coefficient poly ~ r, IsOrderedPolynomial poly) => poly -> (poly, poly)

# Documentation

class (CoeffRing (Coefficient poly), Eq poly, DecidableZero poly, KnownNat (Arity poly), Module (Scalar (Coefficient poly)) poly, Ring poly, Commutative poly) => IsPolynomial poly where Source #

Polynomial in terms of free associative commutative algebra generated
by n-elements.
To effectively compute all terms, we need

in addition to
universality of free object.`monomials`

type Coefficient poly :: Type Source #

Coefficient ring of polynomial type.

type Arity poly :: Nat Source #

Arity of polynomial type.

liftMap :: (Module (Scalar (Coefficient poly)) alg, Ring alg, Commutative alg) => (Ordinal (Arity poly) -> alg) -> poly -> alg Source #

Universal mapping for free algebra. This corresponds to the algebraic substitution operation.

subst :: (Ring alg, Commutative alg, Module (Scalar (Coefficient poly)) alg) => Sized (Arity poly) alg -> poly -> alg Source #

substWith :: Ring m => (Coefficient poly -> m -> m) -> Sized (Arity poly) m -> poly -> m Source #

Another variant of

.
This function relies on `liftMap`

; if you have more efficient implementation,
it is encouraged to override this method.`terms'`

Since 0.6.0.0

sArity' :: poly -> SNat (Arity poly) Source #

Arity of given polynomial.

sArity :: proxy poly -> SNat (Arity poly) Source #

Arity of given polynomial, using type proxy.

arity :: proxy poly -> Integer Source #

Non-dependent version of arity.

injectCoeff :: Coefficient poly -> poly Source #

Inject coefficient into polynomial.

injectCoeff' :: proxy poly -> Coefficient poly -> poly Source #

Inject coefficient into polynomial with result-type explicitly given.

monomials :: poly -> HashSet (Monomial (Arity poly)) Source #

returns the finite set of all monomials appearing in `monomials`

f`f`

.

terms' :: poly -> Map (Monomial (Arity poly)) (Coefficient poly) Source #

returns the finite set of all terms appearing in `monomials`

f`f`

;
Term is a finite map from monomials to non-zero coefficient.

coeff' :: Monomial (Arity poly) -> poly -> Coefficient poly Source #

`'coeff m f'`

returns the coefficient of monomial `m`

in polynomial `f`

.

constantTerm :: poly -> Coefficient poly Source #

Calculates constant coefficient.

fromMonomial :: Monomial (Arity poly) -> poly Source #

Inject monic monomial.

toPolynomial' :: (Coefficient poly, Monomial (Arity poly)) -> poly Source #

Inject coefficient with monomial.

polynomial' :: Map (Monomial (Arity poly)) (Coefficient poly) -> poly Source #

Construct polynomial from the given finite mapping from monomials to coefficients.

totalDegree' :: poly -> Natural Source #

Returns total degree.

var :: Ordinal (Arity poly) -> poly Source #

returns a polynomial representing n-th variable.`var`

n

mapCoeff' :: (Coefficient poly -> Coefficient poly) -> poly -> poly Source #

Adjusting coefficients of each term.

(>|*) :: Monomial (Arity poly) -> poly -> poly infixl 7 Source #

`m `

multiplies polynomial `>|*`

f`f`

by monomial `m`

.

(*|<) :: poly -> Monomial (Arity poly) -> poly infixl 7 Source #

Flipped version of `(`

`>|*`

)

(!*) :: Coefficient poly -> poly -> poly infixl 7 Source #

_Terms' :: Iso' poly (Map (Monomial (Arity poly)) (Coefficient poly)) Source #

mapMonomial :: (Monomial (Arity poly) -> Monomial (Arity poly)) -> poly -> poly Source #

class (IsMonomialOrder (Arity poly) (MOrder poly), IsPolynomial poly) => IsOrderedPolynomial poly where Source #

Class to lookup ordering from its (type-level) name.

coeff :: OrderedMonomial (MOrder poly) (Arity poly) -> poly -> Coefficient poly Source #

A variant of

which takes `coeff'`

instead of `OrderedMonomial`

`Monomial`

terms :: poly -> Map (OrderedMonomial (MOrder poly) (Arity poly)) (Coefficient poly) Source #

The default implementation is not enough efficient.
So it is strongly recomended to give explicit
definition to

.`terms`

leadingTerm :: poly -> (Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly)) Source #

Leading term with respect to its monomial ordering.

leadingMonomial :: poly -> OrderedMonomial (MOrder poly) (Arity poly) Source #

Leading monomial with respect to its monomial ordering.

leadingCoeff :: poly -> Coefficient poly Source #

Leading coefficient with respect to its monomial ordering.

orderedMonomials :: poly -> Set (OrderedMonomial (MOrder poly) (Arity poly)) Source #

The collection of all monomials in the given polynomial, with metadata of their ordering.

fromOrderedMonomial :: OrderedMonomial (MOrder poly) (Arity poly) -> poly Source #

A variant of

which takes `fromMonomial`

as argument.`OrderedMonomial`

toPolynomial :: (Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly)) -> poly Source #

A variant of

which takes `toPolynomial'`

as argument.`OrderedMonomial`

polynomial :: Map (OrderedMonomial (MOrder poly) (Arity poly)) (Coefficient poly) -> poly Source #

A variant of

which takes `polynomial'`

as argument.`OrderedMonomial`

The default implementation combines

and `mapKeys`

,
hence is not enough efficient. So it is strongly recomended to give explicit
definition to `polynomial'`

.`polynomial`

(>*) :: OrderedMonomial (MOrder poly) (Arity poly) -> poly -> poly infixl 7 Source #

A variant of `'(>|*)'`

which takes

as argument.`OrderedMonomial`

(*<) :: poly -> OrderedMonomial (MOrder poly) (Arity poly) -> poly infixl 7 Source #

Flipped version of (>*)

_Terms :: Iso' poly (Map (OrderedMonomial (MOrder poly) (Arity poly)) (Coefficient poly)) Source #

diff :: Ordinal (Arity poly) -> poly -> poly Source #

`diff n f`

partially diffrenciates `n`

-th variable in the given polynomial `f`

.
The default implementation uses

and `terms`

and is really naive; please consider overrideing for efficiency.`polynomial`

mapMonomialMonotonic :: (OrderedMonomial (MOrder poly) (Arity poly) -> OrderedMonomial (MOrder poly) (Arity poly)) -> poly -> poly Source #

Same as

, but maping function is
assumed to be strictly monotonic (i.e. `mapMonomial`

`a < b`

implies `f a < f b`

).

substCoeff :: IsPolynomial poly => Sized (Arity poly) (Coefficient poly) -> poly -> Coefficient poly Source #

liftMapCoeff :: IsPolynomial poly => (Ordinal (Arity poly) -> Coefficient poly) -> poly -> Coefficient poly Source #

class (DecidableZero r, Ring r, Commutative r, Eq r) => CoeffRing r Source #

Constraint synonym for rings that can be used as polynomial coefficient.

## Instances

(DecidableZero r, Ring r, Commutative r, Eq r) => CoeffRing r Source # | |

oneNorm :: (IsPolynomial poly, Normed (Coefficient poly), Monoidal (Norm (Coefficient poly))) => poly -> Norm (Coefficient poly) Source #

1-norm of given polynomial, taking sum of

s of each coefficients.`norm`

maxNorm :: (IsPolynomial poly, Normed (Coefficient poly)) => poly -> Norm (Coefficient poly) Source #

Maximum norm of given polynomial, taking maximum of the

s of each coefficients.`norm`

monoize :: (Field (Coefficient poly), IsOrderedPolynomial poly) => poly -> poly Source #

Make the given polynomial monic. If the given polynomial is zero, it returns as it is.

sPolynomial :: (IsOrderedPolynomial poly, Field (Coefficient poly)) => poly -> poly -> poly Source #

calculates the S-Polynomial of given two polynomials.`sPolynomial`

pDivModPoly :: (k ~ Coefficient poly, Euclidean k, IsOrderedPolynomial poly) => poly -> poly -> (poly, poly) Source #

`pDivModPoly f g`

calculates the pseudo quotient and reminder of `f`

by `g`

.

content :: (IsPolynomial poly, Euclidean (Coefficient poly)) => poly -> Coefficient poly Source #

The content of a polynomial f is the

of all its coefficients.`gcd`

pp :: (Euclidean (Coefficient poly), IsPolynomial poly) => poly -> poly Source #

calculates the primitive part of given polynomial `pp`

f`f`

,
namely `f / content(f)`

.

injectVars :: ((Arity r <= Arity r') ~ True, IsPolynomial r, IsPolynomial r', Coefficient r ~ Coefficient r') => r -> r' Source #

vars :: forall poly. IsPolynomial poly => [poly] Source #

class Show r => PrettyCoeff r where Source #

Coefficients which admits pretty-printing

showsCoeff :: Int -> r -> ShowSCoeff Source #

## Instances

data ShowSCoeff Source #

Pretty-printing conditional for coefficients.
Each returning

must not have any sign.`ShowS`

showsCoeffAsTerm :: ShowSCoeff -> ShowS Source #

showsCoeffWithOp :: ShowSCoeff -> ShowS Source #

showsPolynomialWith :: (IsPolynomial poly, PrettyCoeff (Coefficient poly)) => Sized (Arity poly) String -> Int -> poly -> ShowS Source #

:: IsPolynomial poly | |

=> Bool | Whether print multiplication as |

-> (Int -> Coefficient poly -> ShowSCoeff) | Coefficient printer |

-> Sized (Arity poly) String | Variables |

-> Int | Precision |

-> poly | Polynomial |

-> ShowS |

showPolynomialWith :: (IsPolynomial poly, PrettyCoeff (Coefficient poly)) => Sized (Arity poly) String -> Int -> poly -> String Source #

showPolynomialWith' :: IsPolynomial poly => Bool -> (Int -> Coefficient poly -> ShowSCoeff) -> Sized (Arity poly) String -> Int -> poly -> String Source #

# Polynomial division

divModPolynomial :: (IsOrderedPolynomial poly, Field (Coefficient poly)) => poly -> [poly] -> ([(poly, poly)], poly) infixl 7 Source #

Calculate a polynomial quotient and remainder w.r.t. second argument.

divPolynomial :: (IsOrderedPolynomial poly, Field (Coefficient poly)) => poly -> [poly] -> [(poly, poly)] infixl 7 Source #

A Quotient of given polynomial w.r.t. the second argument.

modPolynomial :: (IsOrderedPolynomial poly, Field (Coefficient poly)) => poly -> [poly] -> poly infixl 7 Source #

Remainder of given polynomial w.r.t. the second argument.

# Conversion between polynomial types

convertPolynomial :: (IsOrderedPolynomial poly, IsOrderedPolynomial poly', Coefficient poly ~ Coefficient poly', MOrder poly ~ MOrder poly', Arity poly ~ Arity poly') => poly -> poly' Source #

Conversion between polynomials with the same monomial orderings, coefficents and variables.

convertPolynomial' :: (IsOrderedPolynomial poly, IsOrderedPolynomial poly', Coefficient poly ~ Coefficient poly', Arity poly ~ Arity poly') => poly -> poly' Source #

Conversion between polynomials with the same monomial coefficents and variables.

mapPolynomial :: (IsOrderedPolynomial poly, IsOrderedPolynomial poly') => (Coefficient poly -> Coefficient poly') -> (Ordinal (Arity poly) -> Ordinal (Arity poly')) -> poly -> poly' Source #

# Default instances

isUnitDefault :: (DecidableUnits r, Coefficient poly ~ r, IsPolynomial poly) => poly -> Bool Source #

recipUnitDefault :: (DecidableUnits r, Coefficient poly ~ r, IsPolynomial poly) => poly -> Maybe poly Source #

isAssociateDefault :: (UnitNormalForm r, Coefficient poly ~ r, IsOrderedPolynomial poly) => poly -> poly -> Bool Source #

splitUnitDefault :: (UnitNormalForm r, Coefficient poly ~ r, IsOrderedPolynomial poly) => poly -> (poly, poly) Source #