Ring

Contents

Description

Dieses Modul stellt die zentrale Typklasse Ring fuer kommutative Ringe mit Eins und einige spezialisierte Klassen zur Verfuegung.

Synopsis

Typklassen fuer Ringe und Ringe mit bestimmten Eigenschaften

class Ring a where

Klasse fuer Typen, die Ringe repraesentieren. Dabei meinen wir stets kommutative Ringe mit Eins.

Methods

(+) ∷ a → a → a

Addition.

negate ∷ a → a

Negation.

(*) ∷ a → a → a

Multiplikation.

zero ∷ a

Null.

unit ∷ a

Eins.

fromInteger ∷ Integer → a

fromInteger z soll das Bild von z unter dem eindeutigen Ringhomomorphismus vom Ring der ganzen Zahlen in a, also z 1, sein.

couldBeNonZero ∷ a → Bool

Bei der Rechnung mit Polynomen sammeln sich manchmal abschliessende Null-Koeffizienten an, die weggelassen werden koennten. Da wir nicht fordern wollen, dass jeder Ring diskret ist (etwa weil das nicht stimmt oder der Test auf Gleichheit teuer ist), gehen wir hier einen Kompromiss:

Ein Ring kann die Methode couldBeNonZero implementieren. Diese soll nur dann False zurueckliefern, wenn das uebergebene Ringelement null ist. Sie ist aber nicht gezwungen, in diesem wirklich False zurueckzugeben -- in der Tat ist die Standardimplementierung einfach 

 couldBeNonZero = const True.

Die zu erfuellende Spezifikation ist also: 

 couldBeNonZero x == False  ==>  x == zero.

Ringe, fuer die es einen effizienten Gleichheitstest mit Null gibt, koennen couldBeNonZero entsprechend besser definieren.

Instances

Ring Int 
Ring Integer 
Ring ComplexRational 
(IntegralDomain a, Integral a) ⇒ Ring (Ratio a) 
Ring a ⇒ Ring (F a) 
Ring a ⇒ Ring (ER a) 
Ring a ⇒ Ring (Poly a) 
(Ring ex, Eq ex) ⇒ Ring (AST ex) 
(RingMorphism m, HasAnnihilatingPolynomials (Domain m)) ⇒ Ring (IC m) 
Ring (IC m) ⇒ Ring (Alg m) 
ReifyPoly p ⇒ Ring (SE p) 
(ReifyNat n, Ring a) ⇒ Ring (SqMatrix n a) 
Ring k ⇒ Ring (ISE k s) 

(-) ∷ Ring a ⇒ a → a → a

Subtraktion, erfuellt folgende Spezifikation: 

 x - y = x + negate y.

class (Ring a, Eq a) ⇒ IntegralDomain a

Klasse fuer Typen, die Integritaetsbereiche repraesentieren, also fuer alle x folgende Bedingung erfuellen: Entweder ist x null, oder x ist regulaer (d.h. die Multiplikationsabbildung mit x ist injektiv).

Aus dieser Definition folgt sofort, dass Gleichheit im Ring entscheidbar (fuer gegebene Ringelemente x, y muss nur die Frage stellen, ob x-y null oder regulaer ist), daher fordern wir die Zugehoerigkeit zur Eq-Typklasse.

Bestimmte Methoden muss ein Typ, der zur IntegralDomain-Klasse gehoeren moechte, nicht haben: Denn da in einem Integritaetsbereich ein Element genau dann regulaer ist, wenn es nicht null ist, wird die geforderte Entscheidungsfaehigkeit schon durch '(==)' von Eq geliefert.

Instances

class (Ring a, Ord a) ⇒ OrderedRing a

Klasse fuer geordnete Ringe, also Ringe mit einer totalen Relation (<=) (reflexiv, transitiv, antisymmetrisch, je zwei Elemente vergleichbar), die folgende zwei Kompatibilitaetsaxiome erfuellt: 

 a <= b          ==>  a + c <= b + c
 0 <= a, 0 <= b  ==>  0 <= ab.

Instances

OrderedRing (Ratio Integer) 
OrderedRing a ⇒ OrderedRing (F a) 
OrderedRing (Alg QinR) 

class Ring a ⇒ HasTestableAssociatedness a where

Klasse fuer Ringe, in denen entscheidbar ist, ob zwei gegebene Elemente x und y zueinander assoziiert sind, ob es also ein invertierbares Element u mit y = ux gibt.

Methods

areAssociated ∷ a → a → Maybe a

areAssociated x y soll genau dann False sein, wenn x und y nicht zueinander assoziiert sind, und andernfalls Just u zurueckgeben, wobei u ein invertierbares Element mit y = ux (in dieser Reihenfolge) ist.

Richtiger waere es, den Rueckgabetyp auf eine monadischen Typ abzuschwaechen; in den in diesem Projekt betrachteten Faellen koennen wir aber in der Tat sogar den von diesem Typ geforderten funktionalen Zusammenhang bieten.

Instances

class Ring a ⇒ HasRationalEmbedding a where

Klasse fuer Ringe, die eine (dann eindeutige) Einbettung der rationalen Zahlen zulassen.

Methods

fromRational ∷ Rational → a

fromRational q soll das Bild von q unter der Einbettung der rationalen Zahlen in den Ring a sein.

Instances

Ringe mit einer komplexen Konjugation

class (Ring a, Ring (RealSubring a)) ⇒ HasConjugation a where

Klasse fuer Ringe, in denen der Begriff der komplexen Konjugation definiert ist.

Associated Types

type RealSubring a ∷ *

Zugehoeriger Unterring der reellen Elemente, also solcher, die von der komplexen Konjugation invariant gelassen werden.

Methods

conjugate ∷ a → a

Konjugiert ein Ringelement.

imagUnit ∷ a

Liefert die imaginaere Einheit.

realPart ∷ a → RealSubring a

Liefert den Realteil.

Daraus wird dann auch absSq und imagPart definiert.

imagPart ∷ HasConjugation a ⇒ a → RealSubring a

Bestimmt den Imaginaerteil einer Zahl.

Ist vordefiniert ueber realPart; wenn das zu einer nicht-terminierenden Rekursion fuehrt, muss die Instanz eine geeignete andere Definition gebeen.

Instances

absSq ∷ HasConjugation a ⇒ a → RealSubring a

Berechnet das Betragsquadrat einer Zahl z, also das Produkt von z mit seinem komplex Konjugierten.

Naeherungen fuer Debugging-Zwecke

class HasFloatingApprox a where

Klasse fuer Ringe, die fuer Debuggingzwecke eine Approximation durch komplexe Fliesskommazahlen zulassen.

Methods

unsafeApprox ∷ a → Complex Double

Liefert eine Approximation durch eine komplexe Fliesskommazahl. Diese Methode ist nur fuer Debuggingzwecke gedacht; die Wahl der Genauigkeit bleibt den Instanzen ueberlassen. Auch muss unsafeApprox nicht referentiell-transparent sein.

Instances

Allgemeine Funktionen fuer Ringe

sum ∷ Ring a ⇒ [a] → a

Summiert eine endliche Liste von Ringelementen, mit der Konvention sum [] = zero.

product ∷ Ring a ⇒ [a] → a

Multipliziert eine endliche Liste von Ringelementen, mit der Konvention product [] = unit.

(^) ∷ Ring a ⇒ a → Nat → a

Potenziert ein gegebenes Ringelement mittels binaerer Exponentiation (square and multiply).

Quelle: Das Haskell-Prelude.

QuickCheck-Eigenschaften

props_ringAxioms ∷ (Ring a, Eq a, Arbitrary a, Show a) ⇒ Proxy a → [Property]

props_areAssociated ∷ (HasTestableAssociatedness a, Eq a, Show a, Arbitrary a) ⇒ Proxy a → [Property]

check_Ring ∷ IO ()