halg-polynomials-0.6.0.0: Polynomial rings and basic Gröbner basis computation, part of halg computational algebra suite.

Safe HaskellNone
LanguageHaskell2010

Algebra.Ring.Polynomial.Univariate

Description

Polynomial type optimized to univariate polynomial.

Synopsis

Documentation

data Unipol r Source #

Univariate polynomial. It uses IntMap as its internal representation; so if you want to treat the power greater than maxBound :: Int, please consider using other represntation.

Instances
Unital r => IsLabel "x" (Unipol r) Source #

By this instance, you can use #x for the unique variable of Unipol r.

Instance details

Methods

fromLabel :: Unipol r #

(DecidableZero r, RightModule Integer r) => RightModule Integer (Unipol r) Source # 
Instance details

Methods

(*.) :: Unipol r -> Integer -> Unipol r #

(DecidableZero r, RightModule Natural r) => RightModule Natural (Unipol r) Source # 
Instance details

Methods

(*.) :: Unipol r -> Natural -> Unipol r #

(DecidableZero r, LeftModule Integer r) => LeftModule Integer (Unipol r) Source # 
Instance details

Methods

(.*) :: Integer -> Unipol r -> Unipol r #

(DecidableZero r, LeftModule Natural r) => LeftModule Natural (Unipol r) Source # 
Instance details

Methods

(.*) :: Natural -> Unipol r -> Unipol r #

(Eq r, DecidableZero r) => Eq (Unipol r) Source # 
Instance details

Methods

(==) :: Unipol r -> Unipol r -> Bool #

(/=) :: Unipol r -> Unipol r -> Bool #

CoeffRing r => Num (Unipol r) Source # 
Instance details

Methods

(+) :: Unipol r -> Unipol r -> Unipol r #

(-) :: Unipol r -> Unipol r -> Unipol r #

(*) :: Unipol r -> Unipol r -> Unipol r #

negate :: Unipol r -> Unipol r #

abs :: Unipol r -> Unipol r #

signum :: Unipol r -> Unipol r #

fromInteger :: Integer -> Unipol r #

(Ord r, DecidableZero r) => Ord (Unipol r) Source # 
Instance details

Methods

compare :: Unipol r -> Unipol r -> Ordering #

(<) :: Unipol r -> Unipol r -> Bool #

(<=) :: Unipol r -> Unipol r -> Bool #

(>) :: Unipol r -> Unipol r -> Bool #

(>=) :: Unipol r -> Unipol r -> Bool #

max :: Unipol r -> Unipol r -> Unipol r #

min :: Unipol r -> Unipol r -> Unipol r #

(CoeffRing r, PrettyCoeff r) => Show (Unipol r) Source # 
Instance details

Methods

showsPrec :: Int -> Unipol r -> ShowS #

show :: Unipol r -> String #

showList :: [Unipol r] -> ShowS #

(Eq r, Field r) => UFD (Unipol r) Source # 
Instance details
(Eq r, Field r) => PID (Unipol r) Source # 
Instance details

Methods

egcd :: Unipol r -> Unipol r -> (Unipol r, Unipol r, Unipol r) #

(Eq r, Field r) => IntegralDomain (Unipol r) Source # 
Instance details

Methods

divides :: Unipol r -> Unipol r -> Bool #

maybeQuot :: Unipol r -> Unipol r -> Maybe (Unipol r) #

(Eq r, Field r) => GCDDomain (Unipol r) Source # 
Instance details

Methods

gcd :: Unipol r -> Unipol r -> Unipol r #

reduceFraction :: Unipol r -> Unipol r -> (Unipol r, Unipol r) #

lcm :: Unipol r -> Unipol r -> Unipol r #

(Eq r, Field r) => Euclidean (Unipol r) Source # 
Instance details

Methods

degree :: Unipol r -> Maybe Natural #

divide :: Unipol r -> Unipol r -> (Unipol r, Unipol r) #

quot :: Unipol r -> Unipol r -> Unipol r #

rem :: Unipol r -> Unipol r -> Unipol r #

(Eq r, Field r) => ZeroProductSemiring (Unipol r) Source # 
Instance details
(Eq r, Field r) => UnitNormalForm (Unipol r) Source # 
Instance details

Methods

splitUnit :: Unipol r -> (Unipol r, Unipol r) #

(CoeffRing r, DecidableZero r) => Ring (Unipol r) Source # 
Instance details

Methods

fromInteger :: Integer -> Unipol r

(CoeffRing r, DecidableZero r) => Rig (Unipol r) Source # 
Instance details

Methods

fromNatural :: Natural -> Unipol r #

DecidableZero r => DecidableZero (Unipol r) Source # 
Instance details

Methods

isZero :: Unipol r -> Bool #

(Eq r, Field r) => DecidableUnits (Unipol r) Source # 
Instance details

Methods

recipUnit :: Unipol r -> Maybe (Unipol r) #

isUnit :: Unipol r -> Bool #

(^?) :: Integral n => Unipol r -> n -> Maybe (Unipol r) #

(Eq r, Field r) => DecidableAssociates (Unipol r) Source # 
Instance details

Methods

isAssociate :: Unipol r -> Unipol r -> Bool #

(CoeffRing r, Unital r) => Unital (Unipol r) Source # 
Instance details

Methods

one :: Unipol r #

pow :: Unipol r -> Natural -> Unipol r #

productWith :: Foldable f => (a -> Unipol r) -> f a -> Unipol r #

(CoeffRing r, Commutative r) => Commutative (Unipol r) Source # 
Instance details
(CoeffRing r, DecidableZero r) => Semiring (Unipol r) Source # 
Instance details
(CoeffRing r, Multiplicative r) => Multiplicative (Unipol r) Source # 
Instance details

Methods

(*) :: Unipol r -> Unipol r -> Unipol r #

pow1p :: Unipol r -> Natural -> Unipol r #

productWith1 :: Foldable1 f => (a -> Unipol r) -> f a -> Unipol r #

DecidableZero r => Monoidal (Unipol r) Source # 
Instance details

Methods

zero :: Unipol r #

sinnum :: Natural -> Unipol r -> Unipol r #

sumWith :: Foldable f => (a -> Unipol r) -> f a -> Unipol r #

(DecidableZero r, Group r) => Group (Unipol r) Source # 
Instance details

Methods

(-) :: Unipol r -> Unipol r -> Unipol r #

negate :: Unipol r -> Unipol r #

subtract :: Unipol r -> Unipol r -> Unipol r #

times :: Integral n => n -> Unipol r -> Unipol r #

DecidableZero r => Additive (Unipol r) Source # 
Instance details

Methods

(+) :: Unipol r -> Unipol r -> Unipol r #

sinnum1p :: Natural -> Unipol r -> Unipol r #

sumWith1 :: Foldable1 f => (a -> Unipol r) -> f a -> Unipol r #

(DecidableZero r, Abelian r) => Abelian (Unipol r) Source # 
Instance details
Hashable r => Hashable (Unipol r) Source # 
Instance details

Methods

hashWithSalt :: Int -> Unipol r -> Int #

hash :: Unipol r -> Int #

NFData r => NFData (Unipol r) Source # 
Instance details

Methods

rnf :: Unipol r -> () #

CoeffRing r => IsPolynomial (Unipol r) Source # 
Instance details

Associated Types

type Coefficient (Unipol r) :: Type #

type Arity (Unipol r) :: Nat #

Methods

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

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

substWith :: Ring m => (Coefficient (Unipol r) -> m -> m) -> Sized (Arity (Unipol r)) m -> Unipol r -> m #

sArity' :: Unipol r -> SNat (Arity (Unipol r)) #

sArity :: proxy (Unipol r) -> SNat (Arity (Unipol r)) #

arity :: proxy (Unipol r) -> Integer #

injectCoeff :: Coefficient (Unipol r) -> Unipol r #

injectCoeff' :: proxy (Unipol r) -> Coefficient (Unipol r) -> Unipol r #

monomials :: Unipol r -> HashSet (Monomial (Arity (Unipol r))) #

terms' :: Unipol r -> Map (Monomial (Arity (Unipol r))) (Coefficient (Unipol r)) #

coeff' :: Monomial (Arity (Unipol r)) -> Unipol r -> Coefficient (Unipol r) #

constantTerm :: Unipol r -> Coefficient (Unipol r) #

fromMonomial :: Monomial (Arity (Unipol r)) -> Unipol r #

toPolynomial' :: (Coefficient (Unipol r), Monomial (Arity (Unipol r))) -> Unipol r #

polynomial' :: Map (Monomial (Arity (Unipol r))) (Coefficient (Unipol r)) -> Unipol r #

totalDegree' :: Unipol r -> Natural #

var :: Ordinal (Arity (Unipol r)) -> Unipol r #

mapCoeff' :: (Coefficient (Unipol r) -> Coefficient (Unipol r)) -> Unipol r -> Unipol r #

(>|*) :: Monomial (Arity (Unipol r)) -> Unipol r -> Unipol r #

(*|<) :: Unipol r -> Monomial (Arity (Unipol r)) -> Unipol r #

(!*) :: Coefficient (Unipol r) -> Unipol r -> Unipol r #

_Terms' :: Iso' (Unipol r) (Map (Monomial (Arity (Unipol r))) (Coefficient (Unipol r))) #

mapMonomial :: (Monomial (Arity (Unipol r)) -> Monomial (Arity (Unipol r))) -> Unipol r -> Unipol r #

CoeffRing r => IsOrderedPolynomial (Unipol r) Source # 
Instance details

Associated Types

type MOrder (Unipol r) :: Type #

(DecidableZero r, Semiring r) => RightModule (Scalar r) (Unipol r) Source # 
Instance details

Methods

(*.) :: Unipol r -> Scalar r -> Unipol r #

(DecidableZero r, Semiring r) => LeftModule (Scalar r) (Unipol r) Source # 
Instance details

Methods

(.*) :: Scalar r -> Unipol r -> Unipol r #

type Arity (Unipol r) Source # 
Instance details
type Arity (Unipol r) = 1
type Coefficient (Unipol r) Source # 
Instance details
type Coefficient (Unipol r) = r
type MOrder (Unipol r) Source # 
Instance details
type MOrder (Unipol r) = Grevlex

naiveMult :: (DecidableZero r, Multiplicative r) => Unipol r -> Unipol r -> Unipol r Source #

Polynomial multiplication, naive version.

karatsuba :: forall r. CoeffRing r => Unipol r -> Unipol r -> Unipol r Source #

Polynomial multiplication using Karatsuba's method.

coeffList :: Monoidal k => Unipol k -> [k] Source #

The list of coefficients, in ascending order.

divModUnipolByMult :: (Eq r, Field r) => Unipol r -> Unipol r -> (Unipol r, Unipol r) Source #

divModUnipol :: (CoeffRing r, Field r) => Unipol r -> Unipol r -> (Unipol r, Unipol r) Source #

mapCoeffUnipol :: DecidableZero b => (a -> b) -> Unipol a -> Unipol b Source #

liftMapUnipol :: (Module (Scalar k) r, Monoidal k, Unital r) => (Ordinal 1 -> r) -> Unipol k -> r Source #