Algebra.Ring.Polynomial.Univariate

Polynomial type optimized to univariate polynomial.

Documentation

data Unipol r

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)

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

Methods

fromLabel :: Proxy# Symbol "x" -> Unipol r

(DecidableZero r, LeftModule Integer r) => LeftModule Integer (Unipol r)

Methods

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

(DecidableZero r, LeftModule Natural r) => LeftModule Natural (Unipol r)

Methods

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

(DecidableZero r, RightModule Integer r) => RightModule Integer (Unipol r)

Methods

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

(DecidableZero r, RightModule Natural r) => RightModule Natural (Unipol r)

Methods

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

(Eq r, DecidableZero r) => Eq (Unipol r)

Methods

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

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

CoeffRing r => Num (Unipol r)

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)

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)

Methods

showsPrec :: Int -> Unipol r -> ShowS

show :: Unipol r -> String

showList :: [Unipol r] -> ShowS

(Eq r, Field r) => IntegralDomain (Unipol r)

Methods

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

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

(Eq r, Field r) => GCDDomain (Unipol r)

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) => UFD (Unipol r)

(Eq r, Field r) => PID (Unipol r)

Methods

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

(Eq r, Field r) => Euclidean (Unipol r)

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

(CoeffRing r, Commutative r) => Commutative (Unipol r)

(Eq r, Field r) => UnitNormalForm (Unipol r)

Methods

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

(Eq r, Field r) => ZeroProductSemiring (Unipol r)

(CoeffRing r, DecidableZero r) => Ring (Unipol r)

Methods

fromInteger :: Integer -> Unipol r

(CoeffRing r, DecidableZero r) => Rig (Unipol r)

Methods

fromNatural :: Natural -> Unipol r

DecidableZero r => DecidableZero (Unipol r)

Methods

isZero :: Unipol r -> Bool

(Eq r, Field r) => DecidableUnits (Unipol r)

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)

Methods

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

(CoeffRing r, Unital r) => Unital (Unipol r)

Methods

one :: Unipol r

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

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

(DecidableZero r, Group r) => Group (Unipol r)

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

(CoeffRing r, Multiplicative r) => Multiplicative (Unipol r)

Methods

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

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

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

(CoeffRing r, DecidableZero r) => Semiring (Unipol r)

DecidableZero r => Monoidal (Unipol r)

Methods

zero :: Unipol r

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

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

DecidableZero r => Additive (Unipol r)

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)

Hashable r => Hashable (Unipol r)

Methods

hashWithSalt :: Int -> Unipol r -> Int

hash :: Unipol r -> Int

NFData r => NFData (Unipol r)

Methods

rnf :: Unipol r -> ()

CoeffRing r => IsOrderedPolynomial (Unipol r)

Associated Types

type MOrder (Unipol r) :: *

Methods

coeff :: OrderedMonomial * (MOrder (Unipol r)) (Arity (Unipol r)) -> Unipol r -> Coefficient (Unipol r)

terms :: Unipol r -> Map (OrderedMonomial * (MOrder (Unipol r)) (Arity (Unipol r))) (Coefficient (Unipol r))

leadingTerm :: Unipol r -> (Coefficient (Unipol r), OrderedMonomial * (MOrder (Unipol r)) (Arity (Unipol r)))

leadingMonomial :: Unipol r -> OrderedMonomial * (MOrder (Unipol r)) (Arity (Unipol r))

leadingCoeff :: Unipol r -> Coefficient (Unipol r)

orderedMonomials :: Unipol r -> Set (OrderedMonomial * (MOrder (Unipol r)) (Arity (Unipol r)))

fromOrderedMonomial :: OrderedMonomial * (MOrder (Unipol r)) (Arity (Unipol r)) -> Unipol r

toPolynomial :: (Coefficient (Unipol r), OrderedMonomial * (MOrder (Unipol r)) (Arity (Unipol r))) -> Unipol r

polynomial :: Map (OrderedMonomial * (MOrder (Unipol r)) (Arity (Unipol r))) (Coefficient (Unipol r)) -> Unipol r

(>*) :: OrderedMonomial * (MOrder (Unipol r)) (Arity (Unipol r)) -> Unipol r -> Unipol r

(*<) :: Unipol r -> OrderedMonomial * (MOrder (Unipol r)) (Arity (Unipol r)) -> Unipol r

_Terms :: Iso' (Unipol r) (Map (OrderedMonomial * (MOrder (Unipol r)) (Arity (Unipol r))) (Coefficient (Unipol r)))

diff :: Ordinal Nat (Arity (Unipol r)) -> Unipol r -> Unipol r

mapMonomialMonotonic :: (OrderedMonomial * (MOrder (Unipol r)) (Arity (Unipol r)) -> OrderedMonomial * (MOrder (Unipol r)) (Arity (Unipol r))) -> Unipol r -> Unipol r

CoeffRing r => IsPolynomial (Unipol r)

Associated Types

type Coefficient (Unipol r) :: *

type Arity (Unipol r) :: Nat

Methods

liftMap :: (Module (Scalar (Coefficient (Unipol r))) alg, Ring alg, Commutative alg) => (Ordinal Nat (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 :: (Unital r, Monoidal m) => (Coefficient (Unipol r) -> r -> m) -> Sized (Arity (Unipol r)) r -> 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 Nat (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

(DecidableZero r, Semiring r) => LeftModule (Scalar r) (Unipol r)

Methods

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

(DecidableZero r, Semiring r) => RightModule (Scalar r) (Unipol r)

Methods

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

ConwayPolynomial p n => Reifies * (Conway Nat Nat p n) (Unipol (F Nat p))

Methods

reflect :: proxy (Unipol (F Nat p)) -> a

type MOrder (Unipol r)

type MOrder (Unipol r) = Grevlex

type Coefficient (Unipol r)

type Coefficient (Unipol r) = r

type Arity (Unipol r)

type Arity (Unipol r) = 1

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

Polynomial multiplication, naive version.

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

Polynomial multiplication using Karatsuba's method.

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

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

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

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

module Algebra.Ring.Polynomial.Class

module Algebra.Ring.Polynomial.Monomial