Unendliche Listen als Grenzwerte

... [ Seminar "Einführung in die funktionale Programmiersprache Haskell" ] ... [ Inhaltsverzeichnis ] ... [ Zurück ] ... [ Weiter ] ...

Übersicht: Unendliche Listen als Grenzwerte

Allgemeines

 In der Mathematik werden oft unendliche Objekte als Grenzwerte für unendliche Sequenzen von Approximationen verwendet. Beispielsweise wird die irrationale Zahl 
π = 3.141592653589...
als Grenzwert der unendlichen Sequenz der rationalen Approximationen 
 3, 3.1, 3.14, 3.141, 3.1415, ...
definiert. Jede einzelne dieser Zahlen ist eine Approximation der Zahl π . Unterschiede ergeben sich durch die Genauigkeit der einzelnen Approximationen. So ist z.B. das erste Element, die 3, eine ziemlich grobe Approximation der Zahl π. Die Qualität der einzelnen Approximationen nimmt von links nach rechts laufend mit jedem Element zu.

Genau wie in diesem Beispiel aus der Mathematik kann eine unendliche Liste als Grenzwert für eine Sequenz von Approximationen betrachtet werden. Wird z.B. die unendliche Liste [1 ..] als Grenzwert der unendlichen Sequenz der Teillisten 
 ⊥, 1:⊥, 1:2:⊥, 1:2:3:⊥, ...
angesehen, so stellt jede Teilliste von links nach rechts betrachtet eine bessere Approximation für [1 ..] dar, als die vorangehende Liste. Das erste Element, in diesem Fall das undefinierte Element ⊥ , ist Bestandteil jeder unendlichen Liste und damit nur eine sehr grobe Approximation. Die Teilliste 1:⊥ hingegen ist insofern eine bessere Approximation, dass sie zumindest das erste Element des Grenzwertes bestimmt. Der Rest der Liste wird auch hier nicht näher spezifiziert, weshalb die nachfolgenden Approximationen wiederum weiter an Qualität zunehmen. Deutlich wird auf jeden Fall, dass eine bessere Approximation dadurch erreicht wird, dass das undefinierte Element durch einen besser definierten Wert ersetzt wird und somit mehr Informationen über den Grenzwert liefert. Es existieren auch Approximationssequenzen, die sich im Gegensatz zu den bereits angesprochenen keinem Grenzwert annähern. Ein Beispiel für solch eine Sequenz ist die folgende: 
⊥, 1:⊥, 2:1:⊥, 3:2:1:⊥, ...usw.
In diesem Fall wiedersprechen sich die durch die einzelnen Teillisten gelieferten Informationen. Die zweite Teilliste gibt beispielsweise an, dass der Grenzwert mit 1 beginnt. Die dritte Teilliste hingegen legt die 2 als Startelement fest. Die vierte Liste beginnt dann wiederum mit der 3 usw... Die Approximation liefert also keine eindeutige Information über den zu erwartenden Grenzwert.

Wichtig:
Zu beachten ist, dass der Grenzwert einer Sequenz von Teillisten nicht zwingend unendlich sein muss. Beispielsweise ist die Sequenz ⊥, 1:⊥, [1], [1] , ...usw., in welcher jedes Element nach den ersten beiden [1] lautet, auch eine gültige Sequenz.
In diesem Fall lautet der Grenzwert [1]. Das gleiche Prinzip gilt für 
⊥, 1:⊥, 1:2:⊥, 1:2:⊥, ...
Hier lautet der Grenzwert 
1:2:⊥.
Es wird deutlich:
Auch endliche Listen können als Grenzwerte von Sequenzen fungieren. Allerdings gilt hier die Restriktion, dass diese Sequenzen nur eine endliche Zahl von verschiedenen Elementen enthalten dürfen.

Ordnungen über Approximationen

 Wie breits angesprochen, besteht die Möglichkeit, dass unendliche Sequenzen von Teillisten gegen einen Grenzwert konvergieren. Um diese Eigenschaft formal darzustellen, wird auf die Idee der Definition einer Approximationsordnung ⊆ über die Elemente jedes Typen zurückgegriffen. Der Ausdruck x ⊆ y bedeutet in diesem Fall, dass x eine Approximation von y, d.h. ein Näherungswert von y ist. Die Approximationsordung ⊆ besitzt folgende Eigenschaften:

Reflexivität:  x ⊆ x 

Transitivität: (x ⊆ y) ∧ (y ⊆ z) ⇒ (x ⊆ y)

Antisymmetrie: (x ⊆ y) ∧ (y ⊆ x) ⇒ ( x = y)
Es handelt sich hier um eine partielle Ordnung, da nicht jedes beliebige Elementpaar durch ⊆ verglichen werden kann. Im Folgenden soll kurz erlätert werden, wie die Approximationsordnung ⊆ für verschiedene Typen definiert ist. Für Approximationsordnungen über Zahlen, Booleans, Character und Aufzählungstypen jeglicher Art gilt folgender Satz: 
x ⊆  y  ≡ ( x = ⊥) ∨ ( x = y)
Er sagt aus, dass y durch x approximiert werden kann, falls x das undefinierte Element ⊥ oder gleich y ist. Das undefinierte Element ⊥ kann als Approximation für "alles" verwendet werden. Daher hat sich auch die Bezeichnung "Bottom" Element, zu Deutsch Grundelement bzw. Basiselement durchgesetzt. Die soeben eingeführte Ordnung wird als flach bezeichnet, da abhängig von x alles oder absolut nichts über den zu approximierenden Wert y bekannt ist.
Die Approximationsordnung über den Typen ( α , β ) wird durch 
⊥ ⊆ ( x , y ) und 

( x , y ) ⊆ ( x´ , y´ ) ≡ ( x ⊆ x´) ∧ ( y  ⊆ y´)
definiert. Das Vorkommen von ⊆ auf der rechten Seite bezieht sich jeweils auf die einzelnen Typen α und β . Hierbei handelt es sich um keine flache Ordnung, auch wenn die Ordnungen über die Typen α und β flach sind. 
Bsp.: ( Bool , Bool ) 

⊥ ⊆ ( ⊥ , ⊥ ) ⊆ ( ⊥ , False ) ⊆ ( True , False )
Ordnungen über Listen der Art [α] werden definiert durch 
⊥ ⊆ xs und

[] ⊆ xs ≡ xs = [] 

( x : xs ) ⊆ ( y : ys ) ≡ ( x ⊆ y ) ∧ ( xs ⊆ ys)
Die zweite Definition sagt aus, dass die leere Liste [] nur durch sich selbst approximiert werden kann. Im dritten Fall wird deutlich, dass eine Approximation von ( y : ys ) duch ( x : xs ) nur möglich ist, wenn y duch x und ys duch xs approximiert werden kann. Bei der Approximation von y durch x gilt auch hier wieder die Approximationsordung über α.
Beispiele: 
[ 1 , ⊥ , 3 ] ⊆ [ 1 , 2 , 3 ] und 
[ 1 , 2 , ⊥ ] ⊆ [ 1 , 2 , 3 ]
Die Liste [ 1 , 2 , 3 ] lässt sich jeweils durch die Listen [ 1 , ⊥ , 3 ] und [ 1 , 2 , ⊥ ] approximieren. Zwischen diesen beiden Listen ist jedoch keine Approximationsbeziehung möglich.
Es wird unterstellt, dass die Approximationsordnung für jeden Typ α eine zusätzliche Eigenschaft zu den bereits beschriebenen besitzt. Jede Approximationskette x0 ⊆ x1 ⊆ ... usw. besitzt einen Grenzwert, welcher ebenfalls vom Typ α ist. Dieser Grenzwert, welcher durch die Syntax lim n→∞ xn ausgedrückt wird, erfüllt folgende zwei Bedingungen:

1) xn ⊆ lim n→∞   xn für alle n
⇒ diese Bedingung gibt an, dass der Grenzwert eine obere Grenze der Sequenz von Approximationen ist
2) falls xn ⊆ y für alle n gilt, dann gilt ausserdem lim n→∞  xn ⊆ y.
⇒ Beim Grenzewert handelt es sich also um die niedrigste obere Grenze.

Die Definition für den Grenzwert von Approximationsketten gilt für jeden Typ. Partielle Ordnungen die diese Eigenschaft besitzen werden auch “vollständig” genannt.

Für Listen existiert die Funktion approx, welche Approximatioen für eine gegebene Liste erzeugt.
Die Definition lautet: 
approx   :: Integer -> [α] -> [α]
approx (n+1) [] = []
approx (n+1) (x:xs) = x : approx n xs
Die Definition von approx ist der Definition von take sehr ähnlich . Mit der Ausnahme, dass für den Fall approx 0 xs = ⊥ für alle xs gilt.
Beispiele: 
approx 0 [1] = ⊥
approx 1 [1] = 1 : ⊥
approx 2 [1] = 1 : []
Für n ≥2 gilt approx n [1] = [1]. Allgemein lässt sich diese Eigenschaft wie folgt ausdrücken:
lim n→∞   approx n xs = xs für alle endlichen, partiellen oder unendlichen Listen xs.

 

berechenbare Funktionen

 Es lassen sich viele verschiedene Funktionen definieren, von denen jedoch nur ein Teil berechenbar ist. Berechenbare Funktionen besitzen zwei Eigenschaften, die sie von willkürlich definierten Funktionen unterscheiden. Zunächst einmal ist eine berechenbare Funktion f im Bezug auf die Approximationsordung monoton.
Es gilt also: 
x ⊆ y   ⇒  f x ⊆ f y   für alle x und y
D. h. “ Je mehr Information durch das Argument an die Funktion übergeben werden, desto mehr Information enthält der Rückgabewert der Funktion ”

Als Zweite wichtige Eigenschaft wird Stetigkeit der Funktion vorausgesetzt. Diese wird allgemein durch 
f ( lim n→∞   xn) = lim n→∞   f xn für alle Approximationsketten x0⊆x1⊆x2⊆...usw.
ausgedrückt. Stetigkeit bedeutet in diesem Fall, dass sich bei Anwendung der Funktion f auf die einzelnen Elemente der Approximationskette keine unerwarteten Ergebnisse einstellen.
Beispiel:
Die folgende Sequenz von Approximationen

⊥ , 1 : ⊥ : , 1 : 2 : ⊥ , 1 : 2 : 3 : ⊥ , ...usw.

besitzt als Limit die unendliche Liste [1..]. Nun soll mit Hilfe der Funktion map die Funktion square auf alle Elemente der Liste angewandt werden, um so eine neue Liste zu berechnen.
Die Berechnung von 
map square [1..]
kann auch wie folgt geschehen:
Die Funktion square wird auf alle Elemente der einzelnen Approximationen angewandt, so dass sich folgende neue Sequenz ergibt: 

map square ⊥               = ⊥ 
map square (1 : ⊥)         = 1 : ⊥
map square (1 : 2 : ⊥)     = 1 : 4 : ⊥
map square (1 : 2 : 3 : ⊥) = 1 : 4 : 9 : ⊥
usw...
Das Limit dieser Sequenz lautet [1,4,9,..] und liefert damit das gleiche Ergebnis, als wenn die Funktion square auf die unendliche Liste [1..] angewandt worden wäre.
... [ Seminar "Einführung in die funktionale Programmiersprache Haskell" ] ... [ Inhaltsverzeichnis ] ... [ Zurück ] ... [ Weiter ] ...