Polynomial

Contents

Description

Dieses Modul stellt fuer jeden Ring a seinen Polynomring Poly a in einer Variablen zur Verfuegung.

Synopsis

Typen fuer Polynome und normierte Polynome

newtype Poly a

Typ der Polynome ueber a, repraesentiert durch die zugehoerigen Folgen der Koeffizienten, von niedrigster zur hoechsten Potenz geordnet. Die Darstellung ist wegen moeglicher abschliessender Nuller natuerlich nicht eindeutig.

Constructors

MkPoly [a]

Instances

Functor Poly
(Ring a, Eq a) ⇒ Eq (Poly a)
(Ring a, Eq a, Show a) ⇒ Show (Poly a)
(Arbitrary a, Ring a) ⇒ Arbitrary (Poly a)
HasConjugation a ⇒ HasConjugation (Poly a)
HasRationalEmbedding a ⇒ HasRationalEmbedding (Poly a)
(Field a, Eq a) ⇒ HasTestableAssociatedness (Poly a)
IntegralDomain a ⇒ IntegralDomain (Poly a)
Ring a ⇒ Ring (Poly a)
Field a ⇒ EuclideanRing (Poly a)
Error (Poly k, Poly k)

newtype NormedPoly a

Kennzeichnung fuer normierte Polynome. Dabei sei sogar vereinbart, dass es keine abschliessenden Nuller gibt, also dass der hoechste Koeffizient schon selbst genau 1 ist.

Dient auch zum einfachen Testen von Eigenschaften normierter Polynome, Beispielanwendung:

 forAll arbitrary $ \MkNormedPoly p -> ...

Constructors

MkNormedPoly
Fields unNormedPoly ∷ Poly a

Instances

Functor NormedPoly
(Eq a, Ring a) ⇒ Eq (NormedPoly a)
(Eq a, Show a, Ring a) ⇒ Show (NormedPoly a)
(Arbitrary a, Ring a) ⇒ Arbitrary (NormedPoly a)

mkNormedPoly ∷ (Ring a, Eq a) ⇒ Poly a → NormedPoly a

Kluger Konstruktor fuer NormedPoly: Er prueft, ob wirklich ein normiertes Polynom vorliegt (wirft sonst eine Laufzeitausnahme) und kanonisiert es.

canonCoeffs ∷ (Ring a, Eq a) ⇒ Poly a → [a]

Liefert die Liste der Koeffizienten in kanonisierter Form, also ohne abschliessende Nuller.

canonCoeffs' ∷ Ring a ⇒ NormedPoly a → [a]

Liefert fuer normierte Polynome die Liste der Koeffizienten in kanonisierter Form, also ohne abschliessende Nuller. Anders als canonCoeffs benoetigen wir hier nicht die Diskretheitsvoraussetzung an den Ring, weil wir vereinbart haben, dass Polynome in NormedPoly sogar "echt", also ohne abschliessende Nuller, normiert sind.

unsafeCoeffs ∷ Poly a → [a]

Liefert die Liste der Koeffizienten ohne eine Kanonisierung vorzunehmen. Diese Funktion ist bezueglich der Gleichheit auf Polynomen also nicht referentiell-transparent.

fromBase ∷ a → Poly a

Gibt zu jedem Element sein zugehoeriges konstantes Polynom.

(.*) ∷ Ring a ⇒ a → Poly a → Poly a

Multiplikation mit Skalaren des Grundrings.

iX ∷ Ring a ⇒ Poly a

Die formale Variable des Polynomrings Poly a.

Operationen

eval ∷ Ring a ⇒ a → Poly a → a

Wertet ein Polynom an einer Stelle aus. Das ist bei Ganzheitsringen (bei denen Ganzheitsgleichungen mitgeschleppt werden muessen) ineffizient, siehe IntegralClosure.eval fuer eine bessere Moeglichkeit.

eval0 ∷ Ring a ⇒ Poly a → a

Wertet ein gegebenes Polynom in 0 aus. Ist effizienter, aber semantisch nicht von folgender Spezifikation zu unterscheiden:

 eval0 = eval zero.

content ∷ Poly Rational → Rational

Berechnet den Inhalt eines nicht-verschwindenden Polynoms ueber den rationalen Zahlen.

normedQuotRem ∷ (Ring a, Eq a) ⇒ Poly a → Poly a → (Poly a, Poly a)

Berechnet die Polynomdivision mit Rest fuer den Fall, dass das Nennerpolynom normiert ist. Gegenueber quotRem besitzt diese Variante daher den Vorteil, ueber beliebigen Ringen (statt Koerpern) einsetzbar zu sein.

normalize ∷ (Field a, Eq a) ⇒ Poly a → Poly a

Normiert ein Polynom. Angewendet aufs Nullpolynom wird eine Laufzeitausnahme geworfen.

normalize' ∷ (Field a, Eq a) ⇒ Poly a → NormedPoly a

Normiert ein Polynom und markiert es als solches.

leadingCoeff ∷ (Ring a, Eq a) ⇒ Poly a → a

Liefert den Leitkoeffizienten (konventionsgemaess also niemals null). Auf dem Nullpolynom wird eine Laufzeitausnahme geworfen.

derivative ∷ Ring a ⇒ Poly a → Poly a

Bestimmt die formale Ableitung.

compose

Arguments

∷ Ring a
⇒ Poly a	f
→ Poly a	g
→ Poly a	f . g

Setzt zwei Polynome ineinander ein. Erfuellt folgende Spezifikation:

 eval x (compose f g) = eval (eval x g) f

squarefreePart ∷ Field a ⇒ Poly a → NormedPoly a

Berechnet zu einem gegebenen Polynom f seinen quadratfreien Anteil (als normiertes Polynom), also g mit f = dg, wobei d den groessten gemeinsamen Teiler von f und f' bezeichne.

QuickCheck

normedPolyProp ∷ (Ring a, Eq a) ⇒ NormedPoly a → Bool

Prueft, ob beim gegebenen Polynom die Vereinbarung, dass Elemente von NormedPoly auch ohne Wegwerfen abschliessender Nullkoeffizienten schon normiert sind, erfuellt ist. Nuetzlich zur Formulierung von Tests.

simpleNonconstantRationalPoly ∷ Gen (Poly Rational)

check_Polynomial ∷ IO ()