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
- liftMap :: (Module (Scalar (Coefficient poly)) alg, Ring alg, Commutative alg) => (Ordinal (Arity poly) -> alg) -> poly -> alg
- subst :: (Ring alg, Commutative alg, Module (Scalar (Coefficient poly)) alg) => Sized (Arity poly) alg -> poly -> alg
- substWith :: forall m. Ring m => (Coefficient poly -> m -> m) -> Sized (Arity poly) m -> poly -> m
- sArity' :: poly -> SNat (Arity poly)
- sArity :: proxy poly -> SNat (Arity poly)
- arity :: proxy poly -> Integer
- injectCoeff :: Coefficient poly -> poly
- injectCoeff' :: proxy poly -> Coefficient poly -> poly
- monomials :: poly -> HashSet (Monomial (Arity poly))
- terms' :: poly -> Map (Monomial (Arity poly)) (Coefficient poly)
- coeff' :: Monomial (Arity poly) -> poly -> Coefficient poly
- constantTerm :: poly -> Coefficient poly
- fromMonomial :: Monomial (Arity poly) -> poly
- toPolynomial' :: (Coefficient poly, Monomial (Arity poly)) -> poly
- polynomial' :: Map (Monomial (Arity poly)) (Coefficient poly) -> poly
- totalDegree' :: poly -> Int
- var :: Ordinal (Arity poly) -> poly
- mapCoeff' :: (Coefficient poly -> Coefficient poly) -> poly -> poly
- (>|*) :: Monomial (Arity poly) -> poly -> poly
- (*|<) :: poly -> Monomial (Arity poly) -> poly
- (!*) :: Coefficient poly -> poly -> poly
- _Terms' :: Iso' poly (Map (Monomial (Arity poly)) (Coefficient poly))
- mapMonomial :: (Monomial (Arity poly) -> Monomial (Arity poly)) -> poly -> poly
- class (IsMonomialOrder (Arity poly) (MOrder poly), IsPolynomial poly) => IsOrderedPolynomial poly where
- type MOrder poly :: Type
- coeff :: OrderedMonomial (MOrder poly) (Arity poly) -> poly -> Coefficient poly
- terms :: poly -> Map (OrderedMonomial (MOrder poly) (Arity poly)) (Coefficient poly)
- leadingTerm :: poly -> (Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly))
- leadingMonomial :: poly -> OrderedMonomial (MOrder poly) (Arity poly)
- leadingCoeff :: poly -> Coefficient poly
- splitLeadingTerm :: poly -> (Term poly, poly)
- orderedMonomials :: poly -> Set (OrderedMonomial (MOrder poly) (Arity poly))
- fromOrderedMonomial :: OrderedMonomial (MOrder poly) (Arity poly) -> poly
- toPolynomial :: (Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly)) -> poly
- polynomial :: Map (OrderedMonomial (MOrder poly) (Arity poly)) (Coefficient poly) -> poly
- (>*) :: OrderedMonomial (MOrder poly) (Arity poly) -> poly -> poly
- (*<) :: poly -> OrderedMonomial (MOrder poly) (Arity poly) -> poly
- _Terms :: Iso' poly (Map (OrderedMonomial (MOrder poly) (Arity poly)) (Coefficient poly))
- diff :: Ordinal (Arity poly) -> poly -> poly
- mapMonomialMonotonic :: (OrderedMonomial (MOrder poly) (Arity poly) -> OrderedMonomial (MOrder poly) (Arity poly)) -> poly -> poly
- type Term poly = (Coefficient poly, OMonom poly)
- type OMonom poly = OrderedMonomial (MOrder poly) (Arity poly)
- 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, Module (Scalar r) (Scalar 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', IsPolynomial r, IsPolynomial r', Coefficient r ~ Coefficient r') => r -> r'
- injectVarsAtEnd :: forall r r'. (Arity r <= Arity r', IsPolynomial r, IsPolynomial r', Coefficient r ~ Coefficient r') => r -> r'
- injectVarsOffset :: forall n r r'. ((n + Arity r) <= Arity r', IsPolynomial r, IsPolynomial r', Coefficient r ~ Coefficient r') => SNat n -> r -> r'
- vars :: forall poly. IsPolynomial poly => [poly]
- class Show r => PrettyCoeff r where
- showsCoeff :: Int -> r -> ShowSCoeff
- data ShowSCoeff
- showsCoeffAsTerm :: ShowSCoeff -> ShowS
- showsCoeffWithOp :: ShowSCoeff -> ShowS
- showsPolynomialWith :: (IsOrderedPolynomial poly, PrettyCoeff (Coefficient poly)) => Sized (Arity poly) String -> Int -> poly -> ShowS
- showsPolynomialWith' :: IsOrderedPolynomial poly => Bool -> (Int -> Coefficient poly -> ShowSCoeff) -> Sized (Arity poly) String -> Int -> poly -> ShowS
- showPolynomialWith :: (IsOrderedPolynomial poly, PrettyCoeff (Coefficient poly)) => Sized (Arity poly) String -> Int -> poly -> String
- showPolynomialWith' :: IsOrderedPolynomial poly => Bool -> (Int -> Coefficient poly -> ShowSCoeff) -> Sized (Arity poly) String -> Int -> poly -> String
- divModPolynomial :: forall poly. (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), Functor t, Foldable t) => poly -> t 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
(liftMap, monomials | terms'), (sArity | sArity'), (fromMonomial | toPolynomial' | polynomial')
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 :: forall m. 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
ff
.
terms' :: poly -> Map (Monomial (Arity poly)) (Coefficient poly) Source #
returns the finite set of all terms appearing in monomials
ff
;
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 -> Int 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 >|*
ff
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.
splitLeadingTerm :: poly -> (Term poly, poly) Source #
Splitting leading term, returning a pair of the leading term and the new polynomial with the leading term subtracted.
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
).
type Term poly = (Coefficient poly, OMonom poly) Source #
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, Module (Scalar r) (Scalar 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 # | |
Defined in Algebra.Ring.Polynomial.Class |
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
ff
,
namely f / content(f)
.
injectVars :: (Arity r <= Arity r', IsPolynomial r, IsPolynomial r', Coefficient r ~ Coefficient r') => r -> r' Source #
See also
and injectVarsOffset
.injectVarsAtEnd
injectVarsAtEnd :: forall r r'. (Arity r <= Arity r', IsPolynomial r, IsPolynomial r', Coefficient r ~ Coefficient r') => r -> r' Source #
Similar to
, but injects variables at the end of
the target polynomial ring.injectVars
See also
and injectVars
.injectVarsOffset
injectVarsOffset :: forall n r r'. ((n + Arity r) <= Arity r', IsPolynomial r, IsPolynomial r', Coefficient r ~ Coefficient r') => SNat n -> r -> r' Source #
Similar to
, but injectVars
injects variables into the first but injectVarsOffset
n fn
variables.
See also
and injectVars
.injectVarsAtEnd
vars :: forall poly. IsPolynomial poly => [poly] Source #
class Show r => PrettyCoeff r where Source #
Coefficients which admits pretty-printing
Nothing
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 :: (IsOrderedPolynomial poly, PrettyCoeff (Coefficient poly)) => Sized (Arity poly) String -> Int -> poly -> ShowS Source #
:: IsOrderedPolynomial poly | |
=> Bool | Whether print multiplication as |
-> (Int -> Coefficient poly -> ShowSCoeff) | Coefficient printer |
-> Sized (Arity poly) String | Variables |
-> Int | Precision |
-> poly | Polynomial |
-> ShowS |
showPolynomialWith :: (IsOrderedPolynomial poly, PrettyCoeff (Coefficient poly)) => Sized (Arity poly) String -> Int -> poly -> String Source #
showPolynomialWith' :: IsOrderedPolynomial poly => Bool -> (Int -> Coefficient poly -> ShowSCoeff) -> Sized (Arity poly) String -> Int -> poly -> String Source #
Polynomial division
divModPolynomial :: forall poly. (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), Functor t, Foldable t) => poly -> t 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 #