Monade fuer nicht-deterministische Rechnungen von Approximationsalgorithmen.

Wir verwenden dazu einfach die IO-Monade, weil wir beliebige externe Kommunikation (beispielsweise Nutzereingaben oder Zufallszahlen) erlauben wollen.

Operationen, die den Kontrollfluss beeinflussen (wie beispielsweise forkIO), verbieten wir. (Denn was wuerde so ein Algorithmus bedeuten?)

unsafeRunR m laesst die nicht-deterministische Operation m laufen und gibt ihr Ergebnis zurueck.

Das ist im Allgemeinen gefaehrlich, denn jedes Mal, wenn das Ergebnis dann ausgewertet wird, kann jeweils ein anderer Wert resultieren, da m ja nicht als deterministisch vorausgesetzt wird. Ausserdem werden die Nebeneffekte in m moeglicherweise mehrmals ausgefuehrt.

Verwendet man unsafeRunR in einer Funktion, muss man daher darauf achten, dass der Rueckgabewert nicht von den verschiedenen Ergebnissen von unsafeRunR abhaengt -- sonst verletzt man das Prinzip der referentiellen Transparenz.

Typ der Approximationsalgorithmen mit Approximationen aus ex. Dabei fordern wir folgende Bedingung (die sich aber leider in Haskell nicht auf Typebene festschreiben laesst):

Es muss eine bestimmte Zahl z geben, sodass der Algorithmus, mit einer positiven natuerlichen Zahl n aufgerufen, eine Naeherung an z produziert, deren Abstand zu z echt kleiner als n^(-1) ist.

Ansonsten ist dem Approximationsalgorithmus keinen Beschraenkungen unterworfen. Insbesondere darf er beliebige nicht-deterministische Prozesse anstossen, und kann bei der wiederholten Fragen nach einer n^(-1)-Naeherung jedes Mal ein anderes Resultat liefern.

Klasse fuer Raeume, deren Punkte sich durch Elemente einer gewissen Teilmenge beliebig genau approximieren lassen.

Damit man die Forderung der Approximation formulieren kann, muss man eigentlich auf dem Typ a eine Norm (oder Metrik) gegeben haben. Dann koennten wir aber unser wichtigstes Beispiel, die komplexen Zahlen Complex, nicht mehr unterstuetzen, denn die Ordnung auf Normen komplexer Zahlen (also gewissen reellen Zahlen) ist nicht entscheidbar.

Moeglicherweise koennte man dieses Problem durch eine bessere Definition normierter Raeume beheben.

Erzeugt einen interaktiven Approximationsalgorithmus, welcher Naeherungen dadurch produziert, indem er den Nutzer auf der Standardkonsole fragt.

Erzeugt wie newInteractiveApprox' einen interaktiven Approximationsalgorithmus, wobei als Konsistenzpruefung

 |x_n - x_m| <= 1/n + 1/m

verwendet wird. Diese ist noch zu schwach, aber die Methoden der NormedRing-Klasse erlauben keine Pruefung auf <.

Der Typ der komplexen Zahlen.

Der Typ der reellen Zahlen.

Elemente in AST ex beschreiben Rechnungen (abstract syntax trees), die man mit Werten aus ex, den Ringoperationen (Addition und Multiplikation -- Negation kann man als Multiplikation mit -unit gewinnen) und zusaetzlichen nur durch Approximationsprozeduren gegebenen ideellen Elementen fuehren kann. Die Darstellung ist natuerlich nicht eindeutig, und Gleichheit nicht entscheidbar.

Beispielsweise ist AST ComplexRational der Typ der komplexen Zahlen, AST Rational der der reellen Zahlen -- zumindest wenn man aequivalente Beschreibungen miteinander identifiziert.

AST ex kann man sich auch als die freie Ringerweiterung von ex durch Approximationsprozeduren vorstellen, und man koennte auch kuerzer AST ex durch

 data AST' ex = Exact ex | Ext String (Approx ex)

definieren, denn da Prozeduren vom Typ Approx ex beliebige Rechnungen durchfuehren duerfen, koennen diese die in dieser Alternativdefinition fehlenden Konstruktoren emulieren. Auch moeglich waere

 data AST'' ex = Ext String (Approx ex).

Die hier gegebene Definition hat zwei Vorteile. Zum einen koennen wir so einige rudimentaere Optimierungen vornehmen: Moechte man beispielsweise x_1 + ... + x_n auf Genauigkeit N^(-1) auswerten, benoetigt man bei naiver Klammerung, x_1 + (x_2 + (x_3 + ...)), eine Approximation von x_n mit Genauigkeit (2^n N)^(-1). Bei balancierter Auswertung dagegen benoetigt man von jedem Summanden nur eine Approximation mit Genauigkeit (n N)^(-1).

Zum anderen ist die Definition in der Praxis effizienter: Denn bei den beiden Alternativdefinitionen haeufen sich schon bei kurzen Rechnungen sehr viele Approx-Objekte, welche Bezuege auf ihre Definitionsumgebung enthalten und daher automatische Speicherbereinigung verhindern.

Warnung: Wenn man sich nur fuer die syntaktische Struktur interessiert, ist AST ex natuerlich faktoriell in ex. Von einer allgemeinen Funktion f kann man aber nicht erwarten, dass

 approx n (fmap f ast)

auch eine n^(-1)-Approximation an liftM f (approx n ast) liefert. Damit das garantiert ist, muss f ein lipschitzstetiger Ringhomomorphismus mit Lipschitzkonstante kleinergleich 1 sein, wie beispielsweise f = conjugate oder f = fromRational.

Hebt exakte Werte vom Typ ex in den Typ AST ex.

Bezeichnung fuer die Einbettung der rationalen in die komplexen Zahlen

Bezeichnung fuer die Einbettung der rationalen in die reellen Zahlen

Bezeichnung fuer die Einbettung der komplexrationalen in die komplexen Zahlen

Bestimmt eine obere Schranke (im Sinn von <) fuer den Betrag der gegebenen Zahl.

Mehrmalige Aufrufe dieser Funktion koennen verschiedene obere Schranken produzieren.

Wie bei HasDenseSubset muessten wir eigentlich einen geeigneten Metrik- oder Normkontext fordern.

Klasse fuer Ringe, die im Sinne folgender schwaecheren Definition Koerper sind:

 Fuer alle /x/, die von Null entfernt sind, gibt es ein Inverses von /x/.

Da wir das Konzept der Entferntheit nutzen, muessten wir (wie bei HasDenseSubset genauer erlaeutert) eigentlich einen geeigneten Metrik- oder Normkontext fordern.

Bestimmt das Vorzeichen einer von null entfernten reellen Zahl. Die Auswertung von signum' zero terminiert nicht.

traceEvals name z ist semantisch nicht von z zu unterscheiden, gibt aber bei jeder Auswertung Debugging-Informationen auf die Standardfehlerkonsole aus.

logMaxEval z gibt ein Paar (var, z') zurueck, wobei z' semantisch nicht von z zu unterscheiden ist, aber seine maximalen Approximationsgesuche in der veraenderlichen Variablen var speichert.