Safe Haskell	None
Language	GHC2024

NumHask.Free.Polynomial

Contents

Commutative normal form — ℤ[a]
Noncommutative normal form — ℤ⟨a⟩

Description

Polynomial normal forms for Ring terms.

The free ring on generators a is the noncommutative polynomial ring ℤ⟨a⟩: integer combinations of words in the generators. toWord is its normal form — keys are words, order preserved.

The free commutative ring is ℤ[a], reached from ℤ⟨a⟩ by abelianize (sort each word into a monomial bag). toPolynomial is the composite:

toPolynomial = abelianize . toWord

The factoring keeps the bookkeeping honest: Ring the class does not require commutativity, so the sorted-key Polynomial alone is a sound but incomplete decision procedure for free-Ring equality (it identifies xy with yx). toWord is sound and complete for ℤ⟨a⟩; toPolynomial is sound and complete for ℤ[a].

Synopsis

newtype Polynomial a = Polynomial {
- unPolynomial :: Map [a] Integer
}
toPolynomial :: Ord a => Ring a -> Polynomial a
fromPolynomial :: Polynomial a -> Ring a
evalPolynomial :: (Ring b, FromInteger b) => (a -> b) -> Polynomial a -> b
newtype NCPolynomial a = NCPolynomial {
- unNCPolynomial :: Map [a] Integer
}
toWord :: Ord a => Ring a -> NCPolynomial a
abelianize :: Ord a => NCPolynomial a -> Polynomial a
evalNCPolynomial :: (Ring b, FromInteger b) => (a -> b) -> NCPolynomial a -> b

Commutative normal form — ℤ[a]

newtype Polynomial a Source #

Multivariate polynomial in commutative normal form — ℤ[a].

Keys are sorted monomials (bags of generators); the empty list is the constant term. Values are integer coefficients.

>>> let p = plus (times (embed "x") (embed "y")) (negate (embed "z"))
>>> toPolynomial p
Polynomial {unPolynomial = fromList [(["x","y"],1),(["z"],-1)]}

Constructors

Polynomial
Fields unPolynomial :: Map [a] Integer

Instances

Instances details

Eq a => Eq (Polynomial a) Source #
Instance details Defined in NumHask.Free.Polynomial Methods (==) :: Polynomial a -> Polynomial a -> Bool # (/=) :: Polynomial a -> Polynomial a -> Bool #
Show a => Show (Polynomial a) Source #
Instance details Defined in NumHask.Free.Polynomial Methods showsPrec :: Int -> Polynomial a -> ShowS # show :: Polynomial a -> String # showList :: [Polynomial a] -> ShowS #

toPolynomial :: Ord a => Ring a -> Polynomial a Source #

Normalize a Ring term to commutative polynomial form.

The composite of the faithful normal form and the abelianization. Sound for any Ring target; complete only up to commutativity — the commutator vanishes here:

>>> let comm = minus (times (embed "x") (embed "y")) (times (embed "y") (embed "x"))
>>> toPolynomial comm
Polynomial {unPolynomial = fromList []}

fromPolynomial :: Polynomial a -> Ring a Source #

Reconstruct a Ring term from polynomial normal form.

evalPolynomial :: (Ring b, FromInteger b) => (a -> b) -> Polynomial a -> b Source #

Evaluate a polynomial via a generator assignment.

>>> let p = toPolynomial (plus (times (embed "x") (embed "y")) (negate (embed "z")))
>>> evalPolynomial (\g -> case g of "x" -> 2; "y" -> 3; _ -> 5) p :: Int
1

Noncommutative normal form — ℤ⟨a⟩

newtype NCPolynomial a Source #

Noncommutative polynomial in normal form — ℤ⟨a⟩, the monoid ring of the free monoid on the generators.

Keys are words: generator order is preserved, so xy and yx are distinct keys. This is the faithful normal form for the free Ring. (Ord is for the Map, not for commutativity.)

Constructors

NCPolynomial
Fields unNCPolynomial :: Map [a] Integer

Instances

Instances details

Eq a => Eq (NCPolynomial a) Source #
Instance details Defined in NumHask.Free.Polynomial Methods (==) :: NCPolynomial a -> NCPolynomial a -> Bool # (/=) :: NCPolynomial a -> NCPolynomial a -> Bool #
Show a => Show (NCPolynomial a) Source #
Instance details Defined in NumHask.Free.Polynomial Methods showsPrec :: Int -> NCPolynomial a -> ShowS # show :: NCPolynomial a -> String # showList :: [NCPolynomial a] -> ShowS #

toWord :: Ord a => Ring a -> NCPolynomial a Source #

Normalize a Ring term into ℤ⟨a⟩.

Distributes Times over Plus, pushes Negate to coefficients, collects like words — no sorting, so the commutator survives:

>>> let comm = minus (times (embed "x") (embed "y")) (times (embed "y") (embed "x"))
>>> toWord comm
NCPolynomial {unNCPolynomial = fromList [(["x","y"],1),(["y","x"],-1)]}

abelianize :: Ord a => NCPolynomial a -> Polynomial a Source #

Quotient ℤ⟨a⟩ → ℤ[a]: sort each word into a monomial bag and collect. Coefficients that cancel under the identification are dropped.

evalNCPolynomial :: (Ring b, FromInteger b) => (a -> b) -> NCPolynomial a -> b Source #

Evaluate a noncommutative polynomial via a generator assignment.

Word order is respected, so this is the unique Ring homomorphism ℤ⟨a⟩ → b extending the assignment — lawful for noncommutative targets where evalPolynomial is not.