Stand: 16.1.2001
© 2001 François Bry
Dieses Lehrmaterial wird ausschließlich zur privaten Verwendung
angeboten. Eine nichtprivate Nutzung (z.B. im Unterricht
oder eine Veröffentlichung von Kopien oder Übersetzungen) dieses
Lehrmaterials bedarf der Erlaubnis des Autors.
Zeitplan: Das Kapitel 8 kann in den 16. und 17. Sitzungen behandelt werden.
Überblick:
Moderne Programmiersprachen bieten nicht nur vordefinierte Basistypen (wie z.B. "ganze Zahlen", "Boole'sche Werte" und "Zeichenfolge") sowie zusammengesetzte Typen (wie z.B. die Vektoren-, Verbund- und Listentypen) an, sondern haben ein sogenanntes "erweiterbares Typsystem". Das bedeutet, dass sie die Definition von neuen Typen nach den Anforderungen einer Programmieraufgabe ermöglichen. In diesem Kapitel wird die Definitionvon neuen Typen am Beispiel der Programmiersprache SML eingeführt. Zunächst wird das Hilfsmittel der Deklarationen von Typabkürzungen eingeführt. Dann wird die eigentliche Definition von nichtrekursiven und rekursiven Typen in SML erläutert. Schließlich werden Programmierbeispiele behandelt.
Inhalt:
Wir erinnern kurz an den Begriff "Typ" in Programmiersprachen, der bereits mehrmals, insbesondere in den Abschnitten 2.2 und 5.1 behandelt wurde. Zudem führen wir die Begriffe "(Wert-)Konstruktoren" und "(Wert-)Selektoren" eines zusammengesetzten Typs ein.
Ein Typ (oder Datentyp) bezeichnet eine Menge von Werten. Diese Werte können atomar (wie z.B. die Werte des Typs "ganze Zahlen" int) oder zusammengesetzt (wie z.B. die Werte des Typs "Listen von ganzen Zahlen" int list) sein. Die Wertmenge, die ein Typ bezeichnet, kann endlich (wie z.B. im Falle des Typs "Boole'sche Werte" bool) oder unendlich (wie im Falle des Typs "ganze Zahlen" int) sein. Mit einem Typ werden üblicherweise Prozeduren zur Bearbeitung der Daten des Typs angeboten.
Ein Typ kann atomare Werte haben wie z.B. die Typen bool und int. Ein Typ kann auch zusammengesetzte Werte haben wie z.B. die Typen int * int und der Typ 'a list.
Typen mit zusammengesetzen Werten werden auch zusammengesetzte Typen genannt, weil sie mit zusammengesetzten Typausdrücken wie etwa real * real oder int list oder 'a list bezeichnet werden.
Ein Typ kann vordefiniert sein, d.h. von der Programmiersprache angeboten. Vordefinierte Typen von SML sind z.B. der Typ "ganze Zahlen" int und der Typ "Boole'sche Werte" bool. Moderne Programmiersprachen ermöglichen auch die Definition von neuen Typen nach den Anforderungen einer Programmieraufgabe. Von solchen Programmiersprachen wird gesagt, dass sie ein "erweiterbares Typsystem" haben. Programmiersprachen mit erweiterbaren Typsystemen ermöglichen z.B. die Definition eines Typs "Wochentag", eines Typs "Uhrzeit", eines Typs "komplexe Zahl" oder auch eines Typs "Übungsgruppe" jeweils mit einer geeigneten Wertmenge (diese Beispiele sind näher erläutert im Abschnitt 5.1).
Ein (atomarer oder zusammengesetzter) Typ kann monomorph sein. In diesem Fall kommt keine Typvariable im Typausdruck vor, der ihn bezeichnet. Z.B. sind bool und int * int monomorphe Typen von SML.
Ein (atomarer oder zusammengesetzter) Typ kann auch polymorph sein. In diesem Fall kommen eine oder mehrere Typvariablen im Typausdruck vor, der ihn bezeichnet. Z.B. ist 'a list ein polymorpher Typ von SML.
Mit einem Typ werden (Wert-)Konstruktoren (manchmal auch Operatoren genannt) definiert. Der vordefinierte (polymorphe) Typ "Liste" hat z.B. zwei (Wert-)Konstruktoren: die leere Liste nil und den Operator cons (::).
(Wert-)Konstruktoren können 0-stellig sein oder eine beliebige andere Stelligkeit haben. Der (Wert-)Konstruktor nil des polymorphen Typs "Liste" ist .z.B. 0-stellig. Der (Wert-)Konstruktor cons (::) des selben Typs ist z.B. 2-stellig.
Mit zusammengesetzten Typen werden auch sogenannte "(Wert-)Selektoren" definiert, womit die zusammengesetzten Werte des Typs zerlegt werden können. Die (Wert-)Selektoren des vordefinierten (polymorphen) Typs "Liste" sind die (vordefinierten) Funktionen hd (head) und tl (tail). (Wert-)Selektoren werden manchmal auch "Destruktoren" genannt.
Zur Definition von Typen werden Typkonstruktoren angeboten, womit Typausdrücke zusammengesetzt werden können (siehe Abschnitt 6.5.5).
Typkonstruktoren unterscheiden sich syntaktisch nicht von Funktionen. Typkonstruktoren werden aber anders als Funktionsnamen verwendet:
Vorsicht: Typkonstruktoren sollen nicht mit (Wert-)Konstruktoren verwechselt werden (siehe Abschnitt 6.6).
Im Abschnitt 5.3.2 wurde das folgende Beispiel eines Vektortyps eingeführt:
- type punkt = real * real;
type punkt = real * real
- fun abstand(p1: punkt, p2: punkt) =
let fun quadrat(z) = z * z
val delta_x = #1(p2) - #1(p1)
val delta_y = #2(p2) - #2(p1)
in
Math.sqrt(quadrat(delta_x) + quadrat(delta_y))
end;
val abstand = fn : punkt * punkt -> real
- abstand((4.5, 2.2), (1.5, 1.9));
val it = 3.01496268634 : real
Mit der type-Deklaration
- type punkt = real * real;
wird die Typkonstante punkt als Abkürzung für den Vektortyp real * real vereinbart. Eine solche Abkürzung, "Typabkürzung" (type abbreviation) genannt, spezifiziert keinen neuen Typ, sondern lediglich ein Synonym für einen Typ.
Bietet eine Programmiersprache Typabkürzungen, so sagt man manchmal, dass die Programmiersprache eine "transparente Typbindung" (tranparent type binding) ermöglicht.
Benötigt man z.B. neben Kartesischen Koordinaten auch Polarkoordinaten, dann kann man die folgenden Typabkürzungen vereinbaren:
- type kartes_punkt = real * real;
type kartes_punkt = real * real
- type polar_punkt = real * real;
type polar_punkt = real * real
Da punkt und kartes_punkt beide den selben Typ real * real bezeichnen, ist keine Anpassung der Definition der Funktion abstand an die neueingeführte Typabkürzung kartes_punkt nötig:
- val A = (0.0, 0.0) : kartes_punkt;
val A = (0.0,0.0) : kartes_punkt
- val B = (1.0, 1.0) : kartes_punkt;
val B = (1.0,1.0) : kartes_punkt
- abstand (A, B);
val it = 1.41421356237 : real
Dies mag bequem erscheinen, ist aber gefährlich, weil die Funktion abstand auch auf Punkte in Polarkoordinaten angewendet werden kann, was aus der Sicht der Anwendung keinen Sinn ergibt:
- val C = (1.0, Math.pi/2.0) : polar_punkt;
val C = (1.0,1.57079632679) : polar_punkt
- abstand(B, C);
val it = 0.570796326795 : real
Der Punkt C hat ja die Kartesischen Koordinaten (0.0, 1.0), der Abstand zwischen B und C ist also in Wirklichkeit 1.0.
Die Nützlichkeit von Typabkürzungen ist am Beispiel der Funktionsdeklaration abstand ersichtlich. Würde SML Typabkürzungen nicht ermöglichen, so müsste die Funktion abstand wie folgt definiert werden:
- fun abstand(p1: real * real, p2: real * real) =
let fun quadrat(z) = z * z
val delta_x = #1(p2) - #1(p1)
val delta_y = #2(p2) - #2(p1)
in
Math.sqrt(quadrat(delta_x) + quadrat(delta_y))
end;
val abstand = fn : (real * real) * (real * real) -> real
Diese Definition ist etwas weniger lesbar. Vor allem der ermittelte Typ
(real * real) * (real * real) -> real
der Funktion abstand ist wesentlich schlechter lesbar als
punkt * punkt -> real
Ein zweites Beispiel für die Nützlichkeit von Typabkürzungen ist wie folgt:
- type person = {Name : string,
Vorname : string,
Anschrift : string,
Email : string,
Tel : int};
type person =
{Anschrift:string, Email:string, Name:string,
Tel:int, Vorname:string}
- type kurz_person = {Name : char,
Vorname : char,
Tel : int};
type kurz_person = {Name:char, Tel:int, Vorname:char}
- fun kuerzen(x : person) : kurz_person=
{Name = String.sub(#Name(x), 0),
Vorname = String.sub(#Vorname(x), 0),
Tel = #Tel(x)};
val kuerzen = fn : person -> kurz_person
Obwohl die Typausdrücke
person -> kurz_person
und
{Anschrift:string, Email:string, Name:string, Tel:int, Vorname:string} -> {Name:char, Tel:int, Vorname:char}
den selben Typ bezeichnen, ist der erste Ausdruck lesbarer. Hier noch ein Beispiel für die Verwendung der Funktion:
- kuerzen {Name="Bry", Vorname="Francois",
Anschrift="D1.02", Tel=2210,
Email="bry@informatik.uni-muenchen.de"};
val it = {Name=#"B",Tel=2210,Vorname=#"F"} : kurz_person
Typvariablen dürfen in type-Deklarationen vorkommen. Die Typabkürzungen, die so vereinbart werden, heißen "polymorphe Typabkürzungen". type-Deklarationen, in denen Typvariablen vorkommen, heißen "parametrische type-Deklarationen".
- type 'a menge = 'a -> bool;
type 'a menge = 'a -> bool
- val ziffer_menge : int menge =
fn 0 => true
| 1 => true
| 2 => true
| 3 => true
| 4 => true
| 5 => true
| 6 => true
| 7 => true
| 8 => true
| 9 => true
| _ => false;
val ziffer_menge = fn : int menge
- ziffer_menge(4);
val it = true : bool
- ziffer_menge(~12);
val it = false : bool
Die Sicht einer Menge als Funktion mit der Menge der Boole'schen Werte als Wertbereich ist übrigens in der Mathematik und in der Informatik geläufig. Solche Funktionen werden auch "Charakteristische Funktionen" von Mengen genannt.
Eine Typabkürzung definiert keinen neuen Typ. Neue Typen können in SML mit datatype- und abstype-Deklarationen vereinbart werden. In diesem Kapitel werden nur die Definitionen von neuen Typen mit datatype-Deklarationen behandelt. Die Definition von sogenannten "abstrakten Typen" in SML mit abstype-Deklarationen werden im Kapitel 11 eingeführt.
Ein Typ "Farbe" bestehend aus der Wertmenge {Rot, Gelb, Blau} kann in SML wie folgt definiert werden:
- datatype Farbe = Rot | Gelb | Blau;
datatype Farbe = Blau | Gelb | Rot
- Rot;
val it = Rot : Farbe
Diese Deklaration legt das Folgende fest:
Typen, die mit datatype-Deklarationen definiert werden, sind neue Typen ohne jegliche Entsprechung in vordefinierte Typen. Zudem können ihre (Wert-)Konstruktoren genauso verwendet werden, u.a. für den Musterangleich, wie die (Wert-)Konstruktoren von vordefinierten Typen:
- fun farbname(Rot) = "rot"
| farbname(Gelb) = "gelb"
| farbname(Blau) = "blau";
val farbname = fn : Farbe -> string
- farbname(Gelb);
val it = "gelb" : string
- [Rot, Blau];
val it = [Rot,Blau] : Farbe list
Man beachte, dass die Definition der Funktion farbname einen Fall für jeden (Wert-)Konstruktor des Typs Farbe hat. Um Fehler zu vermeiden und wegen der Lesbarkeit des Programms ist es empfehlenswert, diese Fälle in der Reihenfolge der Typdefinition aufzulisten.
Es ist angebracht, den vordefinierten Typ "Boole'sche Werte" als einen Typ anzusehen, der wie folgt hätte definiert werden können:
- datatype bool = true | false;
Eine solche Typdeklaration mag den unerwünschten Effekt haben, die vordefinierten Funktionen des vordefinierten Typs bool "auszuschalten", weil die Bindung der Typkonstanten bool an den benutzer-definierten Typ die alte Bindung der selben Typkonstante an den vordefinierten Typ "Boole'sche Werte" überschattet.
In SML verfügen benutzer-definierte Typen, die Mengen von atomaren Werten bezeichnen, stets über die Gleichheit, die implizit bei der datatype-Deklaration mit definiert wird:
- Blau = Blau;
val it = true : bool
- Blau = Rot;
val it = false : bool
In SML verfügen benutzer-definierte Typen, die Mengen von atomaren Werten bezeichnen, über keine implizit definierte Ordnung:
- Rot < Gelb;
Error: overloaded variable not defined at type
symbol: <
type: Farbe
Die folgenden Typdeklarationen sind also in SML austauschbar:
- datatype Farbe = Rot | Gelb | Blau;
- datatype Farbe = Gelb | Rot | Blau;
Andere Programmiersprachen würden aus der Reihenfolge der (Wert-)Konstruktoren in der Typdefinition die Ordnung Rot < Gelb < Blau implizit definieren.
Nicht nur Typen, die Mengen von atomaren Werte bezeichnen, können definiert werden, sondern auch Typen mit zusammengesetzten Werten:
- datatype Preis = DM of real | EURO of real;
datatype Preis = DM of real | EURO of real
Diese Deklaration legt das Folgende fest:
- DM(4.5);
val it = DM 4.5 : Preis
- EURO(2.0);
val it = EURO 2.0 : Preis
- DM(1);
Error: operator and operand don't agree [literal]
operator domain: real
operand: int
in expression:
DM 1
Man bachte die Syntax "k of t2" in der Definition eines (Wert-)Konstruktors für einen Typ t1 mit Bereich t2:
datatype t1 = ... | k of t2 | ...
anstelle der Schreibweise k(t2) oder k t2. Diese Syntax unterstreicht, dass ein (Wert-)Konstruktor eines Typs keine gewöhnliche Funktion ist (siehe die Abschnitte 6.5.1 und 8.1.6).
Wie für benutzer-definierte Typen mit atomaren Werten ist der Musterangleich die bevorzugte Weise, Funktionen auf benutzer-definierten Typen mit zusammengesetzten Werten zu definieren:
- fun wechseln(DM(x)) = EURO(0.51129 * x)
| wechseln(EURO(x)) = DM(1.95583 * x);
val wechseln = fn : Preis -> Preis
Wir erinnern daran, dass es empfehlenswert ist, die Fälle beim Musterangleich in der Reihenfolge der Typdefinition aufzulisten.
Die vorangehende Funktion wechseln rundet nach dem 7. Stelle nach dem Komma nicht ab. Unter Verwendung der vordefinierten Funktionen real und round kann wechseln wie folgt verbessert werden:
- fun wechseln(DM(x)) = EURO(real(round(0.51129 * x * 1e5)) * 1e~5)
| wechseln(EURO(x)) = DM(real(round(1.95583 * x * 1e5)) * 1e~5);
In SML verfügen auch benutzer-definierte Typen, die Mengen von zusammengesetzten Werte bezeichnen, über die Gleichheit. Sie ist komponentenweise definiert:
- datatype zeitpunkt = Sek of int | Min of int | Std of int;
datatype zeitpunkt = Min of int | Sek of int | Std of int
- Sek(30) = Sek(0030);
val it = true : bool
- Min(60) = Std(1);
val it = false : bool
- Sek 2 = Sek(2);
val it = true : bool
Die Gleichheit ist auf benutzer-definierten Typen mit zusammengesetzten Werten komponentenweise definiert: Zwei Werte sind gleich, wenn
Ist die Gleichheit auf dem Typ einer Komponenten nicht definiert, so ist sie es auch nicht auf dem benutzer-definierte Typ:
- DM(2.0) = DM(2.0);
Error: operator and operand don't agree [equality type required]
operator domain: ''Z * ''Z
operand: Preis * Preis
in expression:
DM 2.0 = DM 2.0
Wir erinnern daran, dass in SML die Gleichheit über den Gleitkommazahlen nicht vordefiniert ist (siehe Abschnitt 5.2.2).
Typdeklarationen ermöglichen, Funktionen mit Parametern unterschiedlicher Grundtypen zu definieren:
- datatype nb = Int of int | Real of real;
datatype nb = Int of int | Real of real
- fun round(Int(x)) = Int(x)
| round(Real(x)) = Int(trunc(x));
val round = fn : nb -> nb
- round(Int(56));
val it = Int 56 : nb
- round(Real(56.8976));
val it = Int 56 : nb
Ein weiteres Beispiel der Verwendung des Typs nb ist wie folgt:
- datatype nb = Int of int | Real of real;
- local fun real_abl f x =
let
val delta = 1E~10
in
(f(x + delta) - f(x)) / delta
end;
fun konvertieren(Int(x)) = real(x)
| konvertieren(Real(x)) = x
in
fun abl f (Int(x)) = Real(real_abl f (real(x)))
| abl f (Real(x)) = Real(real_abl f x)
end;
val abl = fn : (real -> real) -> nb -> nb
- abl (fn x => 2.0 * x) (Int(5));
val it = Real 2.00000016548 : nb
- abl (fn x => 2.0 * x) (Real(5.0));
val it = Real 2.00000016548 : nb
Man beachte, dass Ausdrücke, die mit den (Wert-)Konstruktoren Int und Real des Typs nb aufgebaut sind, in Klammern vorkommen. Das ist wegen der Präzedenzen in SML notwendig.
Ein Typ kann auch Werte unbegrenzter (endlicher) Größe haben. Beispiele davon sind die Listen. Ein anderes Beispiel sind die sogenannten "Binärbäume".
Wir erinnern an ein paar Definitionen.
Definition: (gerichteter) Graph
Ein (gerichteter) Graph G ist ein Paar (Kn, Ka) mit Ka Teilmenge von Kn × Kn.
Die Elemente von Kn werden "Knoten" von G genannt. Die Elemente von Ka sind die "Kanten" von G.
Ist Kn leer, so sagt man, dass der Graph G = (Kn, Ka) = ({}, {}) leer ist.
Ist (k1, k2) in Ka, so heißt k2 ein Nachfolger von k1 (in G).
Definition: zusammenhängender Graph
Ein (gerichteter) Graph G=(Kn, Ka) heißt zusammenhängend, wenn es für jedes Paar (ka, ke) von Knoten eine Folge (Pfad genannt) von Knoten k1, ..., kn (n >= 1) in Kn gibt, so dass:
In anderen Worten kann man in einem zusammenhängenden Graph G aus jedem Knoten von G über die Kanten von G jeden anderen Knoten von G erreichen, wobei die Kanten in beliebiger Richtung durchlaufen werden dürfen.
Definition: Zyklus in einem Graph
Ein Zyklus in einem Graph G = (Kn, Ka) ist eine endliche Folge k1, ..., kn (n >= 1) von Knoten von G, so dass
In anderen Worten ist ein Zyklus ein Rundgang durch den Graph über die Kanten des Graphen, bei dem die Richtung der Kanten eingehalten wird.
Definition: Baum, Wurzel, Blatt
Sei K eine Menge. (K ist eine Referenzmenge für die Knoten. Das heißt, dass alle Knoten der Bäume, die im Folgenden definiert werden, Elemente von K sind)
Bäume (mit Knoten in K) werden wie folgt definiert:
Ist m in N\{0} und ist für jedes i in N mit 1 <= i <= m (Kn_i, Ka_i) ein Baum mit Wurzel k_i (mit Knoten in K), so dass die Knotenmengen Kn_i paarweise disjunkt sind, und ist k in K ein "neuer" Knoten, der in keinem Kn_i vorkommt, so ist (Kn, Ka) mit
Kn = {k} vereinigt mit der Vereinigung aller Kn_i
Ka = {(k, k_i) | 1 <= i <= m}
vereinigt mit der Vereinigung aller Ka_i
Die Knoten eines Baumes, die keine Nachfolger haben, heißen "Blätter".
Definition: Binärbaum
Ein Binärbaum B ist ein Baum mit der Eigenschaft: Jeder Knoten von B ist entweder ein Blatt oder hat genau zwei Nachfolger.
Man kann leicht (strukturell induktiv) beweisen (Übung!) und noch leichter anhand von Beispielen sich überzeugen (Übung!), dass
Definition: Wald
Ein Wald ist eine Menge von Bäumen, deren Knotenmengen paarweise disjunkt sind.
Bäume und Wälder sind bei Informatikern sehr beliebt und werden in der Informatik häufig verwendet. Fast alle Bäume werden graphisch so dargestellt, dass ihre Wurzel oben und ihre Blätter unten sind. Eine seltene Ausnahme stellen die Beweisbäume dar (siehe Abschnitt 6.7.4).
Eine Definition wie die vorangehende Definition der Bäume heißt "induktive Definition". Induktive Definitionen bestehen immer aus einem Basisfall oder mehreren Basisfällen (wie der Fall 2 der vorangehenden Definition) und einem Induktionsfall oder mehreren Induktionsfällen (wie der Fall 3 der vorangehenden Definition). Zudem können sie Sonderfälle (wie der Fall 1 der vorangehenden Definition) besitzen. Die Basisfälle bestimmen Anfangsstrukturen. Die Induktionsfälle sind Aufbauregeln. Was aus mathematischer Sicht sich hinter einer induktiven Definition verbirgt, wird u.a. in der Hauptstudiumsvorlesung "Logik für Informatiker" erläutert.
Ist eine Datenstruktur (wie im Abschnitt 8.4.1 die Datenstruktur "Baum") induktiv definiert, so lassen sich oft Algorithmen über dieser Datenstruktur leicht rekursiv spezifizieren.
Die Anzahl der Knoten eines Baumes kann z.B. leicht wie folgt rekursiv ermittelt werden:
Rekursive Funktion knotenanzahl zur Berechnung der Anzahl der Knoten eines Baumes
Kn = {k} vereinigt mit der Vereinigung aller Kn_i
Ka = {(k, k_i) | 1 <= i <= m}
vereinigt mit der Vereinigung aller Ka_i
Die Spezifikation von rekursiven Algorithmen über induktiv definierten Datenstrukturen ist eine grundlegende Technik der Informatik.
Es ist üblich, Bäume graphisch zu veranschaulichen, indem man die Knoten durch Symbole darstellt und die Kanten als Verbindungslinien dazwischen, wobei die Richtung der Kanten fast immer mit der Richtung von oben nach unten gleichgesetzt wird:
k1
/ \
k2 k3
/ \ / \
k4 k5 k6 k7
/ \
k8 k9
Dieser Baum ist ein Binärbaum mit Wurzel k1 und Blättern k4, k5, k6, k8, k9. In vielen Fällen sind die Bezeichner der Knoten irrelevant, so dass man an Stelle von k1, k2 usw. jeweils einfach einen kleinen Kreis zeichnet oder ein Symbol wie *.
Oft wird eine Variante von Bäumen benutzt, bei der die Knoten zusätzlich mit Werten markiert sind, zum Beispiel mit Zahlen. Dann zeichnet man einfach die Markierungen statt der Knoten oder *.
4
/ \
1 5
/ \ / \
1 3 5 8
/ \
8 9
Die Werte, mit denen die Knoten in diesem Fall markiert sind, können mehrfach im Baum vorkommen, während die Knoten selbst nicht mehrfach vorkommen können.
In der Informatik werden auch Bäume benutzt, bei denen nur die Blätter mit Werten markiert sind, so dass sich eine Mischform zur Darstellung ergibt:
*
/ \
* *
/ \ / \
1 3 5 *
/ \
8 9
Eine andere Methode der Darstellung beruht auf Ausdrücken, wobei die Kanten des Baums durch die Verschachtelung von Teilausdrücken dargestellt werden. Der obige Baum ohne Markierungen von Knoten kann zum Beispiel so dargestellt werden:
Knt(Knt(Blt,
Blt),
Knt(Blt,
Knt(Blt,
Blt)))
Dieser Ausdruck ist mit zwei verschiedenen Symbolen gebildet, mit denen Blätter und andere Knoten unterschieden werden können. Es ist üblich, aber auch nur eine Konvention, dass die Reihenfolge der Argumente in den Ausdrücken der Reihenfolge der Nachfolger in der graphischen Darstellung entspricht. Da man überdies die Struktur von verschachtelten Ausdrücken durch Einrückungen verdeutlicht, wirkt die Darstellung durch Ausdrücke so als sei sie durch eine Spiegelung aus der graphischen entstanden. Das wird deutlicher, wenn man die Darstellung durch Ausdrücke für die Varianten mit Markierungen betrachtet. Dazu sind lediglich zusätzliche Argumente für die Markierungen erforderlich:
Knt(4,
Knt(1,
Blt(1),
Blt(3)),
Knt(5,
Blt(5),
Knt(8,
Blt(8),
Blt(9))))
Natürlich kann man hier ebenso wie in der graphischen Darstellung auch Varianten betrachten, in denen nur die Blätter mit Werten markiert sein können.
In SML können nichtleere Binärbäume, deren Blätter mit ganzen Zahlen markiert sind, wie folgt spezifiziert werden:
- datatype binbaum1 = Blt of int (* Blt für Blatt *)
| Knt of binbaum1 * binbaum1; (* Knt für Knoten *)
datatype binbaum1 = Blt of int
| Knt of binbaum1 * binbaum1
- val b = Knt(Knt(Blt(1), Blt(3)),
Knt(Blt(5), Knt(Blt(8), Blt(9))));
val b = Knt (Knt (Blt #,Blt #),
Knt (Blt #,Knt #)) : binbaum1
Man beachte, dass der Wert von b abgekürzt gedruckt wird. Die Abkürzung betrifft lediglich die interaktive Treiberschleife von SML. In der globalen Umgebung ist der richtige Wert abgespeichert.
Dieser Binärbaum kann wie folgt graphisch dargestellt werden:
*
/ \
Knt(Blt(1), Blt(3)) * * Knt(Blt(5), Knt(Blt(8), Blt(9)))
/ \ / \
1 3 5 * Knt(Blt(8), Blt(9))
/ \
8 9
Der (Wert-)Konstruktor Knt bildet aus zwei Binärbäumen einen neuen Binärbaum. Sein Typ ist also binbaum1 * binbaum1 -> binbaum1.
Ein solcher Binärbaum wird "beblättert" genannt, weil seine Blätter und nur seine Blätter Markierungen (d.h. Werte) tragen. Im Abschnitt 8.6 wird eine andere Art von Binärbäumen eingeführt, der Binärbaum mit Knotenmarkierungen, deren Knoten alle Markierungen (d.h. Werte) tragen.
Die obige Typdefinition der Binärbäume hat genau die selbe Struktur wie die Definition der Bäume in Abschnitt 8.4.1. Inhaltlich unterscheidet sie sich von der Definition in Abschnitt 8.4.1 lediglich in der zusätzlichen Einschränkung, dass jeder Knoten, der kein Blatt ist, genau zwei Nachfolger haben muss. Syntaktisch unterscheidet sie sich von der Definition vom Abschnitt 8.4.1 in der Verwendung von SML-Konstrukten. Eine Typdefinition wie die Definition des Typs binbaum1 ist also eine induktive Definition.
Wegen ihrer syntaktischen Ähnlichkeit mit rekursiven Algorithmen werden aber solche Typdefinition in der Informatik manchmal "rekursive Typdefinitionen" genannt.
Die Typen, die mittels induktiven (oder rekursiven) Typdefinitionen vereinbart werden, heißen "rekursive Typen".
Die Funktion blaetterzahl zur Berechnung der Anzahl der Blätter eines Binärbaums vom Typ binbaum1 kann in SML wie folgt implementiert werden:
- fun blaetterzahl (Blt(_)) = 1
| blaetterzahl (Knt(b1, b2)) = blaetterzahl b1
+ blaetterzahl b2;
val blaetterzahl = fn : binbaum1 -> int
- val c = Knt(Blt(1), Blt(2));
- blaetterzahl(c);
val it = 2 : int
- blaetterzahl(Knt(c, Knt(c, c)));
val it = 6 : int
Es ist oft vorteilhaft, rekursive Typen polymorph zu definieren. Ein polymorpher Typ binbaum1 kann wie folgt definiert werden:
- datatype 'a binbaum2 = Blt of 'a
| Knt of 'a binbaum2 * 'a binbaum2;
datatype 'a binbaum2 = Blt of 'a
| Knt of 'a binbaum2 * 'a binbaum2
Die Funktion blaetterzahl kann nun wie folgt als polymorphe Funktion wiederdefiniert werden:
- fun blaetterzahl (Blt(_)) = 1
| blaetterzahl (Knt(b1, b2)) = blaetterzahl b1
+ blaetterzahl b2;
val blaetterzahl = fn : 'a binbaum2 -> int
- val d = Knt(Blt("ab"), Blt("cd"));
val d = Knt (Blt "ab",Blt "cd") : string binbaum2
- blaetterzahl(d);
val it = 2 : int
- let val e = Knt(d, d);
val f = Knt(e, e)
in
blaetterzahl(Knt(f, f))
end;
val it = 16 : int
- val g = Knt(Blt([1,2,3]), Blt[4,5]);
val g = Knt (Blt [1,2,3],Blt [4,5]) : int list binbaum2
- let val h = Knt(g, g);
val i = Knt(h, h)
in
blaetterzahl(Knt(i, i))
end;
val it = 16 : int
Mit dem folgenden Prädikat kann überprüft werden, ob ein Element in einem beblätterten Binärbaum vorkommt:
- fun suche(x, Blt(M)) = (x = M)
| suche(x, Knt(B1, B2)) = suche(x, B1)
orelse suche(x, B2);
val suche = fn : 'a * binbaum2 -> bool
- val b = Knt(Knt(Blt(1), Blt(3)), Knt(Blt(5), Knt(Blt(8), Blt(9))));
val b = Knt (Knt (Blt #,Blt #),Knt (Blt #,Knt #)) : int binbaum2
- suche(5, b);
val it = true : bool
- suche(12, b);
val it = false : bool
Die Liste ist ein Sonderfall des beblätterten Binärbaums, wie der Vergleich der Folgenden Darstellungen erkennen läßt:
:: *
/ \ / \
1 :: 1 *
/ \ / \
2 :: 2 *
/ \ / \
3 nil 3 nil
In der Tat besteht die Suche durch einen beblätterten Binärbaum einer solchen Gestalt in den selben Schritten wie die Suche durch eine Liste mit der Funktion member.
Die Frage stellt sich, wie Eigenschaften von Funktionen bewiesen werden können, die auf rekursiven Typen definiert sind. Es ist bemerkenswert, dass Induktionsbeweise (siehe Abschnitt 2.3.6) und induktive Definitionen eine ähnliche Gestalt haben:
In der Tat lassen sich Eigenschaften von Funktionen, die auf rekursiven Typen definiert sind, oft induktiv beweisen. Das Beweisprinzip der vollständigen Induktion, das im Abschnitt 2.3.6 eingeführt wurde, bezieht sich auf natürliche Zahlen. Das Beweisprinzip, das hier anzuwenden ist, heißt "strukturelle Induktion":
Sei t ein rekursiver Typ mit den (Wert-)Konstruktoren k^(s_i)_i (0 <= i <= I) wobei s_i die Stelligkeit des (Wert-)Konstruktors k^(s_i)_i ist.
Um zu zeigen, dass alle Werte des Typs t eine Eigenschaft E (wie etwa "die Auswertung einer Anwendung der Funktion f auf den Wert terminiert") besitzen, genügt es, zu zeigen:
Basisfälle: Jeder 0-stellige (Wert-)Konstruktor k^0_i (0 <= i <= I) besitzt die Eigenschaft E.
Induktionsfälle:
Für jeden (Wert-)Konstruktor k^(s_i)_i (der Stelligkeit s_i) mit i >= 1 gilt: wenn s_i Werte W_1, ...,W_(s_i) des Typs t die Eigenschaft E besitzen (Induktionsanahme), dann besitzt auch der Wert k^(s_i)_i(W_1, ...,W_(s_i)) des Typs t die Eigenschaft E.Das Beweisprinzip der strukturellen Induktion lässt sich auf die vollständige Induktion zurückführen. Dies ist aber keineswegs unmittelbar (siehe die Hauptstudiumsvorlesung Logik für Informatiker).
Als Beispiel einer Anwendung des Beweisprinzips der strukturellen Induktion zeigen wir, dass jede Anwendung der polymorphen Funktion blaetterzahl auf einen Binärbaum vom Typ binbaum1 terminiert:
Basisfall:
Ist A ein Ausdruck der Gestalt Blt(x), so führt die Auswerung von blaetterzahl(A) nach Definition (der Funktion blaetterzahl) zur Auswerung von 1, was offenbar terminiert.
Induktionsfall:
Seien W1 und W2 zwei Werte vom Typ binbaum1.
Induktionsanahmen: Sei angenommen, dass die Auswertungen von blaetterzahl(W1) und von blaetterzahl(W2) beide terminieren.
Nach Definition (der Funktion blaetterzahl) führt die Auswertung von blaetterzahl(Knt(W1, W2)) zur Auswerung von blaetterzahl(W1) + blaetterzahl(W2) Nach Induktionsanahme terminieren die Auswertungen der beiden Komponenten dieser Addition. Folglich terminiert auch die Auswertung dieses Ausdrucks.
QED
In diesem Abschnitt wird untersucht, wie der mathematische Begriff "Menge", der zur Lösung vieler pratischer Aufgaben nützlich ist, in einer Programmiersprache wiedergegeben werden kann.
Zunächst werden die Begriffe "Menge" und "Datenstruktur" erläutert.
Die "Menge" ist ein grundlegender Begriff der Mathematik zur Zusammensetzung von Objekten. Die Zusammensetzung von Objekten als Menge bringt weder eine Reihenfolge noch irgendeine sonstige Strukturierung der Objekte mit sich. Die Objekte, die eine Menge zusammenfasst, werden "Elemente" dieser Menge gennant.
Eine Menge wird immer bezüglich einer "Referenzmenge" definiert, d.h. einer "Urmenge", woraus die Elementen der zu definierenden Mengen stammen. Der Verzicht auf eine Referenzmenge würde Paradoxien ermöglichen, wie etwa das folgende Paradox:
Sei M die (Pseudo-)Menge M, die alle Mengen umfasst, die keine Elementen von sich selbst sind: Gilt M in M?
Falls ja, dann nach Definition von M gilt: M nicht in M, ein Widerspruch.
Falls nein, dann nach Definition von M gilt: M in M, ein Widerspruch.
Die Bedingung, dass keine Menge M definiert werden kann ohne eine Referenzmenge festzulegen, schließt einen solchen Fall aus.
In einer typisierten Programmiersprache stellen die Typen sehr passende Kandidaten für etwaige Referenzmengen dar.
Eine Menge wird "extensional" definiert, wenn ihre Definition aus einer Auflistung ihrer Elemente besteht. So ist z.B. {1, 23, 12.45} eine extensional definierte Menge, deren Referenzmenge R ist.
Eine Menge wird "intensional" definiert, wenn ihre Elementen durch eine Eigenschaft charakterisiert werden. {x * x | x in N} ist z.B. eine intensional definierte Menge, deren Referenzmenge N ist.
Funktionen sind in einer Programmiersprache das Gegenstück zu intensional definierten Mengen. Die Funktion
fun quadrat(x : int) = x * x
drückt in SML die Menge {x * x | x in Z} aus.
Die Datenstruktur "Menge", die es zu implementieren gilt, kann sinnvollerweise also nur extensional definierte, zudem endliche Mengen wiedergeben.
Mit dem Begriff "Menge" werden die folgenden grundlegenden Operationen definiert:
| Elementbeziehung: | in |
| Vereinigung: | M1 U M2 = {x | x in M1 oder x in M2} |
| Durchschnitt: | M1 Schnitt M2 = {x | x in M1 und x in M2} |
| Gleichheit: | Zwei Mengen sind gleich, wenn sie genau die selben Elementen haben. |
| Teilmengebeziehung: | M1 ist eine Teilmenge von M2, wenn jedes Element von M1 auch Element von M2 ist. |
Zudem ist die "leere Menge" eine ausgezeichnete Menge, die keine Elemente hat.
Unter "Datenstruktur" versteht der Informatiker
In einer typisierten Programmiersprache wie SML ist die Definition eines Typs ein gewöhnlicher Teil der Implementierung einer Datenstruktur. Die Definition eines Typs reicht in der Regel nicht aus, weil damit die grundlegenden Operationen der betrachtetenen Struktur noch lange nicht gegeben sind.
In der Praxis besteht die Implementierung einer Datenstruktur am häufigsten aus einem Typ und aus Prozeduren (die nicht immer Funktionen sind), die sich auf diesen Typ beziehen (siehe Kapitel 11 Bildung von Abstraktionsbarrieren mit abstrakten Datentypen).
Im Abschnitt 8.2.5 wurde die Menge der Ziffern wie folgt implementiert:
- type 'a menge = 'a -> bool;
type 'a menge = 'a -> bool
- val ziffer_menge : int menge =
fn 0 => true
| 1 => true
| 2 => true
| 3 => true
| 4 => true
| 5 => true
| 6 => true
| 7 => true
| 8 => true
| 9 => true
| _ => false;
val ziffer_menge = fn : int menge
Eine solche Funktion nennt man, charakterisitische Funktion der Menge (aller Ziffern).
Diese Implementierung gibt die Elementbeziehung unmittelbar wieder. Die Vereinigung und der Durchschnitt lassen sich sehr einfach wie folgt realisieren:
- fun vereinigung(m1:'a menge, m2:'a menge) =
fn x => m1(x) orelse m2(x);
val vereinigung = fn : 'a menge * 'a menge -> 'a -> bool
- fun durchschnitt(m1:'a menge, m2:'a menge) =
fn x => m1(x) andalso m2(x);
val durchschnitt = fn : 'a menge * 'a menge -> 'a -> bool
- val M1 : string menge =
fn "ab" => true
| "bc" => true
| "be" => true
| _ => false;
val M1 = fn : string menge
- val M2 : string menge =
fn "de" => true
| "fg" => true
| "be" => true
| _ => false;
val M2 = fn : string menge
- vereinigung(M1, M2);
val it = fn : string -> bool
- vereinigung(M1, M2)("be");
val it = true : bool
- durchschnitt(M1, M2)("ab");
val it = false : bool
Diese Implementierung ist aber zur Implementierung der Gleichheit (von Mengen) und der Teilmengebeziehung wenig geeignet. Viel geeigneter dafür wäre eine Darstellung der Mengen, die ermöglicht, die Auflistung der Elementen beider Mengen, die auf Gleichheit oder Teilmengebeziehung untersucht werden sollen, direkt zu vergleichen. Da die Auflistung im Programm selbst statt in einem Aufrufparamter vorkommt, ist einer solcher Vergleich in der obigen Implementierung nicht einfach.
Es bietet sich also an, eine extensional definierte, endliche Menge als Liste darzustellen.
Die Elementbeziehung wird durch das im Abschnitt 6.5.7 eingeführte polymorphe Prädikat member implementiert:
- fun member(x, nil) = false
| member(x, head::tail) = if x = head
then true
else member(x, tail);
val member = fn : ''a * ''a list -> bool
- member(3,[1,2,3,4]);
val it = true : bool
Der Zeitbedarf einer Überprüfung einer Elementbeziehung kann wie folgt geschätzt werden. Als Schätzung der Problemgröße bietet sich die Größe (Kardinalität) der Menge an. Als Zeiteinheit bietet sich die Anzahl der rekursiven Aufrufe des Prädikats member an. Zur Überprüfung einer Elementbeziehung bezüglich einer Menge der Kardinalität n wird man bestenfalls member 1 Mal, schlechtestenfalls n+1 Male aufrufen. Der Zeitbedarf einer Überprüfung einer Elementbeziehung ist also schlechtestenfalls O(n).
Die Vereiningung wird durch die im Abschnitt 5.4.7 eingeführte polymorphe Funktion append (in SML als vordefinierte Infixfunktion @ geannt) implementiert:
- fun append(nil, L) = L
| append(h :: t, L) = h :: append(t, L);
val append = fn : 'a list * 'a list -> 'a list
- append([1,2,3], [4,5]);
val it = [1,2,3,4,5] : int list
Diese Implementierung der Vereinigung mag für manche Anwendungen unzufriedenstellend, weil sie die Wiederholung von Elementen nicht ausschließt.
Der Durchschnitt kann wie folgt implementiert werden:
- fun durchschnitt(nil, _) = nil
| durchschnitt(h :: t, L) = if member(h, L)
then h :: durchschnitt(t, L)
else durchschnitt(t, L);
val durchschnitt = fn : ''a list * ''a list -> ''a list
- durchschnitt([1,2,3,4], [3,4,5,6]);
val it = [3,4] : int list
Die Teilmengebeziehung kann wie folgt implementiert werden:
- fun teilmenge(nil, _) = true
| teilmenge(h :: t, L) = if member(h, L)
then teilmenge(t, L)
else false;
val teilmenge = fn : ''a list * ''a list -> bool
- teilmenge([6,4,2],[1,2,8,4,9,6,73,5]);
val it = true : bool
- teilmenge([4,2,3,1], [3,6,5,4]);
val it = false : bool
Um die Menge zu verändern, stehen die Funktionen cons (in SML als Infix-Operator :: vordefiniert), head (in SML als hd vordefiniert) und tail (in SML als tl vordefiniert) zur Verfügung (siehe Abschnitte 5.4.5 und 5.4.6).
Die im vorangehernden Abschnitt eingeführte Implementierung der Menge setzt keineswegs voraus, dass die Listenelemente in auf- oder absteigender Reihenfolge sortiert sind. Eine Sortierung der Elemente setzt selbstverständlich voraus, dass eine Ordnung (d.h. eine reflexive, transitive und antisymmetrische Relation) über der Referenzmenge vorhanden ist, die obendrein total ist, das heißt, dass je zwei beliebige Elemente in der einen oder anderen Richtung zueinander in der Relation stehen. Dies wird im Folgenden angenommen.
Die Frage stellt sich, ob eine Sortierung der Elemente (nach der Ordnung der Referenzmenge) vom Vorteil wäre.
Das ist der Fall. Sind die Elemente nach aufsteigenden (bzw. absteigenden) Werten sortiert, so kann die sequentielle Suche durch die Liste, die das Prädikat member durchführt, abgebrochen werden, sobald ein Listelement gefunden wird, das größer (bzw. kleiner) als das gesuchte Element ist.
Unter der Annahme, dass die Listenelemente nach aufsteigenden Werten sortiert sind, kann die verbesserte Suche wie folgt implementiert werden:
- fun member_sort(x, nil) = false
| member_sort(x, h::t) =
if x < h
then false
else if x = h
then true
else member_sort(x, t);
val member_sort = fn : int * int list -> bool
Schlechtestenfalls wird mit member_sort und einer sortierten Liste sowie member und einer beliebigen Liste die Liste ganz durchlaufen. Schlechtestenfalls benötigt die Suche mit member_sort und einer sortierten Liste eine Zeit, die O(n) ist, wenn n die Länge der Liste ist.
Eine weitere Frage stellt sich: Ermöglicht eine Sortierung der Elemente eine effizientere Suche als die sequentielle Suche mit member_sort?
Die Antwort dazu liefert das Telefonbuch. Wenn man im Telefonbuch nach der Telefonnummer eines Herrn Zimmermann sucht, schlägt man es am Ende auf. Wenn man aber die Telefonnummer eines Herrn Klein erfahren möchte, dann schlägt man das Telefonbuch in der Mitte auf. Und sicherlich wird man das Telefonbuch in seinen Anfangsseiten aufschlagen, wenn man die Telefonnummer eines Herrn Ackermann erfahren möchte.
Da der Bereich der möglichen Namen bekannt ist -- alle Namen fangen mit einem Buchstaben an, der zwischen A und Z liegt -- und die Verteilung der Namen uns einigermaßen vertraut ist -- z.B. fangen deutsche Familiennamen viel häufiger mit K oder S als mit I, N oder O an -- kann man ziemlich schnell in die Nähe des gesuchten Namen kommen.
Es liegt also nahe, anzunehmen, dass die Überprüfung der Elementbeziehung in einer sortierten Liste schneller erfolgen kann als in einer unsortierten Liste.
Diese Überlegung ist aber inkorrekt, weil sortiert sowie unsortiert, eine Liste immer nur linear von ihrem ersten (am linkesten stehenden) Element an durchlaufen werden kann. Die Darstellung der endlichen, extensional definierten Menge als sortierte Liste würde also schlechtenfalls (wie etwa im Falle der Suche nach dem Namen Zimmermann im Telefonbuch) keinen Vorteil gegenüber der Darstellung als unsorteirte Liste bringen. Die Verwendung von sortierten Listen würde sogar einen großen Nachteil mit sich bringen: Den Aufwand für die Sortierung der Elemente.
Betrachten wir wieder einmal das Beispiel der Suche nach einem Namen im Telefonbuch. Verallgemeinern wir zunächst das Beispiel und nehmen wir an, dass der vom Telefonbuch abgedeckte Namensbereich unbekannt ist, d.h. dass es z.B. nicht sicher ist, dass es für jeden möglichen Anfangsbuchstaben überhaupt Namen gibt. Nehmen wir zudem an, dass auch die Namensverteilung völlig beliebig sein kann. Der Verständlichkeit halber kann man auch annehmen, dass das Buch statt Namen (und Telefonnummern) lediglich ganze (d.h. negative sowie positive) Zahlen, die beliebig klein oder gross sein können, (und keine Telefonummern) enthält.
Ohne jegliche Auskunft über den Zahlenbereich, den das Buch abdeckt, und über die Zahlenverteilung im Buch, sucht man nach einer gegebenen Zahl am schnellsten dadurch, dass man das Buch (ungefähr) in seiner Mitte aufschlägt und das Verfahren im linken oder rechten Buchteil (rekursiv) wiederholt, je nach dem, ob die Zahl in der Mitte des Buches größer oder kleiner als die gesuchte Zahl ist.
Eine solche Suche läßt sich anhand von nichtleeren Binärbäumen implementieren, wenn nicht nur die Blätter Zahlen (oder sonstige Werte) tragen (oder damit "markiert" sind), sondern auch die sonstigen Knoten:
- datatype binbaum3 = Blt of int
| Knt of binbaum3 * int * binbaum3;
datatype binbaum3 = Blt of int
| Knt of binbaum3 * int * binbaum3
Man merke, dass dieser Datentyp die leere Menge ausschließt. Dies mag für manche Anwendungen unpassend sein.
- val b1 = Knt(Blt(8),12,Blt(15));
val b1 = Knt (Blt 8,12,Blt 15) : binbaum3
- val b2 = Knt(Blt(32),45,Blt(50));
val b2 = Knt (Blt 32,45,Blt 50) : binbaum3
- val b3 = Knt(b1,21,b2);
val b3 = Knt (Knt (Blt #,12,Blt #),21,Knt (Blt #,45,Blt #)) : binbaum3
Das Zeichen # wird in der gedruckten Mitteilung verwendet, um diese zu kürzen. Diese Kürzung betrifft nur die gedruckte Mitteilung und selbstverständlich nicht den in der Umgebung gespeicherten Wert des Namens b3. Dieser Wert von b3 kann auch wie folgt dargestellt werden:
21
/ \
12 45
/ \ / \
8 15 32 50
In diesem Baum gilt für jeden Knoten, dass alle Markierungen im linken Teilbaum kleiner sind als die Markierung des Knotens und alle Markierungen im rechten Teilbaum größer.
Binärbäume vom Typ binbaum3 haben den Nachteil, nicht alle endlichen Mengen sortiert darstellen zu können. Z.B. können die Mengen {1, 2} und {1,2,3,4} nicht als Binärbaum vom Typ binbaum3 dargestellt werden.
In der Tat kann man unter Anwendung der strukturellen Rekursion beweisen, dass jeder nichtleere Binärbaum vom Typ binbaum3 eine ungerade Anzahl von Knotenmarkierungen hat:
Basisfall:
Ein Binärbaum der Gestalt Blt(W) hat genau eine Knotenmarkierung, also eine ungerade Anzahl von Knotenmarkierungen.
Induktionsfall:
Seien B1 und B2 zwei Binärbäume vom Typ binbaum3 und W eine ganze Zahl.
Induktionsannahme: Jeder von B1 und B2 hat eine ungerade Anzahl von Knotenmarkierungen.
Der Binärbaum Knt(B1, W, B2) hat k = |B1| + 1 + |B2| Knotenmarkjierungen. Da |B1| ungerade ist, gibt es n1 in N mit |B1| = 2 * n1 + 1. Da |B2| ungerade ist, gibt es n2 in N mit |B2| = 2 * n2 + 1. Also k = (2 * n1 + 1) + 1 + (2 * n2 + 1) = 2 * (n1 + n2 + 1) + 1, d.h. k ist ungerade.
QED.
Der folgende Typ binbaum4 beseitigt den Mangel der Binärbäume vom Typ binbaum3.
- datatype binbaum4 = Knt1 of int
| Knt2 of int * int
| Knt3 of binbaum4 * int * binbaum4;
datatype binbaum4
= Knt1 of int | Knt2 of int * int
| Knt3 of binbaum4 * int * binbaum4
- val c0 = Knt2(1,2);
val b2 = Knt2 (1,2) : binbaum4
- val c1 = Knt3(Knt1(1), 2, Knt2(4,3));
val c1 = Knt3 (Knt1 1,2,Knt2 (4,3)) : binbaum4
- val c2 = Knt3(Knt2(1,2), 3, Knt1(4));
val c2 = Knt3 (Knt2 (1,2),3,Knt1 4) : binbaum4
- val d = Knt3(Knt2(1,2), 3, Knt3(Knt1(4), 5, Knt1(6)));
val d = Knt3 (Knt2 (1,2),3,Knt3 (Knt1 #,5,Knt1 #)) : binbaum4
Die Binärbäume c1 und c2 können wie folgt dargestellt werden:
2 3
/ \ / \
1 3 2 4
/ /
4 1
c1 und c2 sind die zwei Möglichkeiten, die Menge {1,2,3,4} als Binärbaum mit sortierten Knotenmarkierungen vom Typ binbaum4 darzustellen.
Der Binärbaum d kann wie folgt dargestellt werden:
3
/ \
2 5
/ / \
1 4 6
* Suche in einem Binärbaum mit sortierten Knotenmarkierungen vom Typ
binbaum4
Betrachten wir die folgenden Binärbäume mit sortierten Knotenmarkierungen vom Typ binbaum4
- val b1 = Knt3(Knt1(8), 12, Knt1(15));
val b1 = Knt3 (Knt1 8,12,Knt1 15) : binbaum4
- val b2 = Knt3(Knt1(32), 45, Knt1(50));
val b2 = Knt3 (Knt1 32,45,Knt1 50) : binbaum4
- val b3 = Knt3(b1, 21, b2);
val b3 = Knt3 (Knt3 (Knt1 #,12,Knt1 #),21,
Knt3 (Knt1 #,45,Knt1 #)) : binbaum4
21
/ \
12 45
/ \ / \
8 15 32 50
Die Suche nach z.B. 25 (bzw. nach 32) in b3 kann wie folgt durchgeführt werden:
Das Verfahren macht nur dann Sinn, wenn die Knotenmarkierungen so sortiert sind, dass für jeden Haupt- oder Teilbaum der Gestalt
Knt2(Markierung1, Markierung2)
gilt:
Markierung1 < Markierung2
und für jeden Haupt- oder Teilbaum der Gestalt
Knt3(LBaum, Markierung, RBaum)
für jeden Knoten Kl im linken LBaum und für jeden Knoten Kr im rechten RBaum gilt:
Kl < Markierung < Kr
Diese Suche in Binärbäumen mit sortierten Knotenmarkierungen vom Typ binbaum4 kann wie folgt implementiert werden:
- fun suche(x, Knt1(M)) = (x = M)
| suche(x, Knt2(M1, M2)) = (x = M1) orelse (x = M2)
| suche(x, Knt3(LBaum, M, RBaum)) =
if x = M
then true
else if x < M
then suche(x, LBaum)
else suche(x, RBaum);
val suche = fn : int * binbaum4 -> bool
- suche(25, b3);
val it = false : bool
- suche(32, b3);
val it = true : bool
- suche(4, d);
val it = true : bool
* Zeitbedarf der Suche in einem Binärbaum mit sortierten Knotenmarkierungen
Der Zeitbedarf der Suche nach einer Zahl in einem Binärbaum mit sortierten Knotenmarkierungen vom Typ binbaum4 kann wie folgt geschätzt werden.
Als Problemgröße bietet sich die Anzahl der Knotenmarkierungen an, d.h. die Kardinalität der Menge, die der Binärbaum mit sortierten Knotenmarkierungen darstellt.
Als Zeiteinheit bietet sich die Anzahl der Knoten an, die besucht werden, bis eine Antwort geliefert wird.
Eine Suche nach einer Zahl in einem Binärbaum mit sortierten Knotenmarkierungen wird also die folgenden Zeiten in Anspruch nehmen:
Offenbar wird eine Suche in einem Binärbaum mit sortierten Knotenmarkierungen die besten Zeiten haben, wenn die Äste des Baumes alle gleich lang sind. Längenunterschiede von einem Knoten zwischen zwei Äste eines Binärbaumes von einem Knoten können offenbar nicht vermieden werden, sonst hätten alle nichtleeren Binärbäume eine ungerade Anzahl an Markierungen (d.h. an Knoten).
Definitionen: Ausgeglichener Baum
Ein Binärbaum vom Typ binbaum4 heißt "ausgeglichen", wenn die Längen von zwei beliebigen seiner Äste sich um höchsten 1 unterscheiden.
Definition: Tiefe
Ein Knoten k eines Baumes hat die Tiefe t, wenn der Pfad von der Wurzel des Baumes zu k t Knoten enthält.
Die Tiefe eines Baumes ist die maximale Tiefe eines seiner Knoten.
Satz A
Die Länge eines Astes von einem ausgeglichenen Binärbaum vom Typ binbaum4, der n Knoten hat, ist O(ln n)
Aus dem Satz A folgt, dass die Suche in einem ausgeglichenen Binärbaum die Zeitkomplexität O(ln) hat, wenn n die Kardinalität der Menge ist.
Der Satz A folgt aus der folgenden Beobachtung:
Satz B
Ein ausgeglichener Binärbaum der Tiefe t kann bis zu 2 ** t Knoten mit Tiefe t haben.
Beweis des Satzes B:
Der Satz B wird wie folgt induktiv bewiesen:
Basisfall:
Es gilt für Binärbäume der Tiefe 0, 1 und 2.
Induktionsfall:
Sei t in N.
Induktionsannahme: Sei angenommen, dass ein ausgeglichener Baum B der Tiefe t bis zu 2 ** t Knoten mit Tiefe t haben kann.
Ein Binärbaum der Tiefe t + 1 besteht aus einer Wurzel mit zwei Nachfolgern, die die Wurzeln von Teilbäumen der Tiefe t sind. Jeder dieser Teilbäume kann nach Induktionsannahme bis zu 2 ** t Knoten mit Tiefe t in dem jeweiligen Teilbaum haben. Diese Knoten sind genau die Knoten mit Tiefe t + 1 im gesamten Baum, zusammen sind es also bis zu 2 * (2 ** t) = 2 ** (t + 1) Knoten.
QED
Beweis des Satzes A:
Aus dem Satz B folgt, dass ein ausgeglichener Binärbaum der Tiefe t maximal 2**0 + 2**1 + ... + 2**t = 2**(t+1) - 1 (Übung!) Knoten hat. Hat also ein ausgeglichener Binärbaum n Knoten, so gilt:
2**t - 1 <= n <= 2**(t+1) - 1
wobei t die Tiefe des Baumes ist. Daraus folgt:
t <= log_2 (n + 1) <= t+1
D.h. t in O(log_2 n+1) = O(K * ln n) für ein K in N, d.h. t in O(ln n).
QED
Wird die Menge durch Hinzufügen oder Löschen von Elementen verändert, so kann nach und nach der Binärbaum, der die Menge darstellt, seine Ausgeglichenheit verlieren. Ein Extremfall von Ausgeglichenheit ist der folgender Baum:
4
/ \
2 5
/ \
1 3
/
0
Dieser Binärbaum läßt sich in SML als Wert des Types binbaum4 wie folgt darstellen:
- val e = Knt3(Knt3(Knt2(0,1), 2, Knt1(3)), 4, Knt1(5));
val e = Knt3 (Knt3 (Knt2 #,2,Knt1 #),4,Knt1 5) : binbaum4
Ein Verfahren ist also nötig, um die Ausgeglichenheit nach jeder oder nach einigen Änderungen der Menge wiederherzustellen. Der Algorithmus dazu ist nicht trivial. Er soll in der Grundstudiumsvorlesung Informatik 2 oder in der Grundstudiumsvorlesung Effiziente Algorithmen eingeführt werden.
Die Funktionen dieses Abschnitts beziehen sich auf den folgenden polymorphen Typ "Binärbaum mit Knotenmarkierungen":
- datatype 'a binbaum5 = Leer
| Knt1 of 'a
| Knt2 of 'a * 'a
| Knt3 of 'a binbaum5 * 'a * 'a binbaum5;
Wir nehmen an, dass in einem Ausdruck Knt2(M1,M2) der Knoten mit Markierung M1 als linker Nachfolger des Knotens mit Markierung M2 aufgefasst werden soll. Betrachten wir die Binärbäume mit folgenden graphischen Darstellungen.
B1: B2: B3: B4: B5:
3 3 3 3 3
/ / \ / \ / \
2 2 5 2 5 2 5
/ /
1 4
B: A:
3 "-"
/ \ / \
2 5 "*" "/"
/ / \ / \ / \
1 4 6 "x" "y" "2" "+"
/ \
"z" "1"
Der Baum A soll offenbar einen arithmetischen Ausdruck repräsentieren. Diese Binärbäume können wie folgt als Ausdrücke des Typs int binbaum5 bzw., im Fall von A, string binbaum5 dargestellt werden:
- val B1 = Knt1( 3);
- val B2 = Knt2(2, 3);
- val B3 = Knt3(Knt1(2), 3, Knt1(5));
- val B4 = Knt3(Knt2(1,2), 3, Knt1(5));
- val B5 = Knt3(Knt1(2), 3, Knt2(4,5));
- val B = Knt3(Knt2(1,2), 3, Knt3(Knt1(4), 5, Knt1(6)));
- val A = Knt3( Knt3( Knt1("x"),
"*",
Knt1("y")
),
"-",
Knt3( Knt1("2"),
"/",
Knt3( Knt1("z"),
"+",
Knt1("1")
)
)
);
In den folgenden Abschnitten werden Funktionen angegeben, die Durchläufen durch Binärbäume (mit Knotenmarkierungen) entsprechen und die Markierungen der Knoten in Listen aufsammeln.
- exception binbaum5_leer;
- exception binbaum5_kein_nachfolger;
- fun wurzel(Leer) = raise binbaum5_leer
| wurzel(Knt1(M)) = M
| wurzel(Knt2(_, M)) = M
| wurzel(Knt3(_, M, _)) = M;
- fun linker_baum(Leer) = raise binbaum5_kein_nachfolger
| linker_baum(Knt1(_)) = raise binbaum5_kein_nachfolger
| linker_baum(Knt2(_, _)) = raise binbaum5_kein_nachfolger
| linker_baum(Knt3(B, _, _)) = B;
- fun rechter_baum(Leer) = raise binbaum5_kein_nachfolger
| rechter_baum(Knt1(_)) = raise binbaum5_kein_nachfolger
| rechter_baum(Knt2(_, _)) = raise binbaum5_kein_nachfolger
| rechter_baum(Knt3(_, _, B)) = B;
- fun ist_leer(Leer) = true
| ist_leer(_) = false;
Damit sind Zugriffe auf Bestandteile von Binärbäumen möglich
- wurzel(B);
val it = 3 : int
- wurzel(rechter_baum(B));
val it = 5 : int
- wurzel(linker_baum(A));
val it = "*" : string
Die folgenden Definitionen sind alle mit Hilfe des Pattern Matching aufgebaut, so dass die obigen Funktionen darin nicht benötigt werden.
Die Infix-Reihenfolge bedeutet, dass zunächst die Knoten des linken Teilbaums, dann die Wurzel, anschließend die Knoten des rechten Teilbaums aufgesammelt werden.
- fun infix_collect(Leer) = nil
| infix_collect(Knt1(M)) = [M]
| infix_collect(Knt2(M1,M2)) = [M1,M2]
| infix_collect(Knt3(B1,M,B2)) =
infix_collect(B1) @ [M] @ infix_collect(B2);
val infix_collect = fn : 'a binbaum5 -> 'a list
- infix_collect(B);
val it = [1,2,3,4,5,6] : int list
- infix_collect(A);
val it = ["x","*","y","-","2","/","z","+","1"] : string list
Die Bezeichnung "Infix-Reihenfolge" wird aus dem Beispiel des Baums A leicht verständlich. Die Ergebnisliste entspricht dem durch den Baum A repräsentierten arithmetischen Ausdruck in Infix-Notation, wobei allerdings die Information über die Klammerung verloren gegangen ist.
Die rechte Seite des letzten Falls der Definition sollte eigentlich umformuliet werden: infix_collect(B1) @ M :: infix_collect(B2); in der obigen Definition wurde trotzdem die umständlichere Form infix_collect(B1) @ [M] @ infix_collect(B2) geschrieben, weil dadurch Analogien und Unterschiede zu den folgenden Funktionen offensichtlicher werden.
Die Präfix-Reihenfolge bedeutet, dass die Wurzel vor den Knoten des linken Teilbaums, und diese vor den Knoten des rechten Teilbaums aufgesammelt werden.
Wir erinnern an die Annahme, dass in einem Ausdruck Knt2(M1, M2) der Knoten M1 linker Nachfolger des Knotens M2 ist.
- fun praefix_collect(Leer) = nil
| praefix_collect(Knt1(M)) = [M]
| praefix_collect(Knt2(M1,M2)) = [M2,M1]
| praefix_collect(Knt3(B1,M,B2)) =
[M] @ praefix_collect(B1) @ praefix_collect(B2);
val praefix_collect = fn : 'a binbaum5 -> 'a list
- praefix_collect(B);
val it = [3,2,1,5,4,6] : int list
- praefix_collect(A);
val it = ["-","*","x","y","/","2","+","z","1"] : string list
Man beachte, dass die Kenntnis der Stelligkeit der Operationen ausreicht, um aus der "Linearisierung" in Präfix-Reihenfolge die im Baum A repräsentierte Klammerung wiederherzustellen.
Auch hier wäre es angebracht, [M] @ praefix_collect(B1) zu vereinfachen zu M :: praefix_collect(B1).
In Postfix-Reihenfolge werden zunächst die Knoten des linken Teilbaums, dann des rechten Teilbaums, und schließlich die Wurzel aufgesammelt.
Wir erinnern an die Annahme, dass in einem Ausdruck Knt2(M1, M2) der Knoten M1 linker Nachfolger des Knotens M2 ist.
- fun postfix_collect(Leer) = nil
| postfix_collect(Knt1(M)) = [M]
| postfix_collect(Knt2(M1,M2)) = [M1,M2]
| postfix_collect(Knt3(B1,M,B2)) =
postfix_collect(B1) @ postfix_collect(B2) @ [M];
val postfix_collect = fn : 'a binbaum5 -> 'a list
- postfix_collect(B);
val it = [1,2,4,6,5,3] : int list
- postfix_collect(A);
val it = ["x","y","*","2","z","1","+","/","-"] : string list
Man beachte, dass die Kenntnis der Stelligkeit der Operationen ausreicht, um aus der "Linearisierung" in Postfix-Reihenfolge die im Baum A repräsentierte Klammerung wiederherzustellen.
Die obigen Definitionen haben ein ähnliches Manko wie die Funktion naive-reverse im Abschnitt 5.4.8. Durch den Aufruf von append in jedem rekursiven Aufruf summiert sich die Gesamtanzahl der Aufrufe von :: auf einen unnötig hohen Wert. Die Funktionen sammeln zwar die Markierungen in der gewünschten Reihenfolge auf, aber verschachtelt in Listen, die dann erst wieder von append zu einer "flachen" liste zusammengefügt werden müssen.
In ähnlicher Weise wie mit Hilfe der Akkumulator-Technik aus der Funktion naive-reverse die Funktion reverse entwickelt wurde, kann man auch hier mit Hilfe der Akkumulator-Technik bessere Definitionen entwickeln:
- fun infix_collect(B) =
let
fun collect(Leer, L) = L
| collect(Knt1(M), L) = M :: L
| collect(Knt2(M1,M2), L) = M1 :: M2 :: L
| collect(Knt3(B1,M,B2), L) = collect(B1, M :: collect(B2, L))
in
collect(B, nil)
end;
val infix_collect = fn : 'a binbaum5 -> 'a list
- fun praefix_collect(B) =
let
fun collect(Leer, L) = L
| collect(Knt1(M), L) = M :: L
| collect(Knt2(M1,M2), L) = M2 :: M1 :: L
| collect(Knt3(B1,M,B2), L) = M :: collect(B1, collect(B2, L))
in
collect(B, nil)
end;
val praefix_collect = fn : 'a binbaum5 -> 'a list
- fun postfix_collect(B) =
let
fun collect(Leer, L) = L
| collect(Knt1(M), L) = M :: L
| collect(Knt2(M1,M2), L) = M1 :: M2 :: L
| collect(Knt3(B1,M,B2), L) = collect(B1, collect(B2, M :: L))
in
collect(B, nil)
end;
val postfix_collect = fn : 'a binbaum5 -> 'a list
Die Reihenfolge, in der die Parameter B1, M, B2 in den rekursiven Aufrufen weitergereicht werden, ist jeweils die gleiche wie in den vorhergehenden Definitionen. Man beachte, dass die lokale Hilfsfunktion collect trotz der Verwendung der Akkumulator-Technik in allen drei Fällen *nicht* endrekursiv ist, weil einer der rekursiven Aufrufe innerhalb eines zusammengesetzten Ausdrucks vorkommt. Ein Durchlauf durch beliebige Binärbäume mit einem iterativen Prozess ist auch gar nicht möglich.
Infix-, Präfix- und Postfix-Reihenfolge haben gemeinsam, dass die Teilbäume des Baums unabhängig voneinander durchlaufen werden. Der Unterschied der Funktionen liegt nur darin, wie das Ergebnis jeweils zusammengesetzt wird. Die Gemeinsamkeit der drei Durchlaufreihenfolgen ist als Tiefendurchlauf bekannt und kann mit Hilfe von Funktionen höherer Ordnung leicht als Abstraktion der drei ursprünglichen Funktionen definiert werden.
- fun depth_first_collect f0 f1 f2 f3 Leer = f0
| depth_first_collect f0 f1 f2 f3 (Knt1(M)) = f1(M)
| depth_first_collect f0 f1 f2 f3 (Knt2(M1,M2)) = f2(M1,M2)
| depth_first_collect f0 f1 f2 f3 (Knt3(B1,M,B2)) =
f3(depth_first_collect f0 f1 f2 f3 B1,
M,
depth_first_collect f0 f1 f2 f3 B2);
- fun infix_collect(B) =
depth_first_collect nil
(fn M => [M])
(fn (M1,M2) => [M1,M2])
(fn (R1,M,R2) => R1 @ [M] @ R2)
B;
- fun praefix_collect(B) =
depth_first_collect nil
(fn M => [M])
(fn (M1,M2) => [M2,M1])
(fn (R1,M,R2) => [M] @ R1 @ R2)
B;
- fun postfix_collect(B) =
depth_first_collect nil
(fn M => [M])
(fn (M1,M2) => [M1,M2])
(fn (R1,M,R2) => R1 @ R2 @ [M])
B;
Aber auch andere nützliche Funktionen auf Binärbäumen lassen sich mit Hilfe des Tiefendurchlaufs leicht implementieren:
- fun anzahl_knoten(B) =
depth_first_collect 0
(fn M => 1)
(fn (M1,M2) => 2)
(fn (R1,M,R2) => R1 + 1 + R2)
B;
- fun anzahl_blaetter(B) =
depth_first_collect 0
(fn M => 1)
(fn (M1,M2) => 1)
(fn (R1,M,R2) => R1 + R2)
B;
- fun tiefe(B) =
depth_first_collect 0
(fn M => 1)
(fn (M1,M2) => 2)
(fn (R1,M,R2) => 1 + Int.max(R1,R2))
B;
- fun element(x,B) =
depth_first_collect false
(fn M => x=M)
(fn (M1,M2) => x=M2 orelse x=M1)
(fn (R1,M,R2) => x=M orelse R1 orelse R2)
B;
- anzahl_knoten(B);
val it = 6 : int
- anzahl_knoten(A);
val it = 9 : int
- anzahl_blaetter(B);
val it = 3 : int
- anzahl_blaetter(A);
val it = 5 : int
- tiefe(B);
val it = 3 : int
- tiefe(A);
val it = 4 : int
- element(5, B);
val it = true : bool
- element(7, B);
val it = false : bool
- element("2", A);
val it = true : bool
- element("3", A);
val it = false : bool
Bei einem Breitendurchlauf werden die Knoten nach wachsender Tiefe besucht. Zuerst wird die Wurzel aufgesammelt, dann die Wurzeln der Nachfolger, dann die Wurzeln von deren Nachfolgern usw. Das Ergebnis des Breitendurchlaufs ist also für Baum B die Liste [3,2,5,1,4,6] und für Baum A die Liste ["-","*","/","x","y","2","+","z","1"].
Zur Implementierung bedienen wir uns einer Hilfsfunktion entwurzeln, die angewandt auf eine Liste von Bäumen von jedem Baum die Wurzel aufsammelt und die Nachfolger der Wurzel am Ende der Liste für die spätere Weiterverarbeitung einfügt. So soll aus der einelementigen Liste von Binärbäumen
nach dem Aufsammeln von "+" die folgende zweielementige Liste entstehen:
[
Knt3(
Knt1("a"),
"*",
Knt1("b")
),
Knt3(
Knt1("e"),
"-",
Knt1("f")
)
]
Die Funktion entwurzeln zerlegt also einen Baum von der Wurzel her, gerade entgegengesetzt zum Aufbau des Baums gemäß der mathematischen Definition oder mit den Konstruktoren des induktiv definierten Typs 'a binbaum5. Der Unterschied zu den Selektoren ist, dass die Teilbäume nicht einfach als Ergebnisse geliefert werden, sondern in einer Liste nach dem Prinzip first-in-first-out verwaltet werden. Der Breitendurchlauf kann wie folgt implementiert werden:
- fun breadth_first_collect(B) =
let
fun entwurzeln nil = nil
| entwurzeln(Leer::L) = entwurzeln(L)
| entwurzeln(Knt1(M)::L) = M ::entwurzeln(L)
| entwurzeln(Knt2(M1,M2)::L) = M2::entwurzeln(L @ [Knt1(M1)])
| entwurzeln(Knt3(B1,M,B2)::L) = M ::entwurzeln(L @ [B1,B2])
in
entwurzeln(B :: nil)
end;
val breadth_first_collect = fn : 'a binbaum5 -> 'a list
- breadth_first_collect(B);
val it = [3,2,5,1,4,6] : int list
- breadth_first_collect(A);
val it = ["-","*","/","x","y","2","+","z","1"] : string list
Beim Breitendurchlauf werden die Teilbäume nicht unabhängig voneinander durchlaufen, sondern nach Tiefe verzahnt. Das verletzt die Grundannahme des Tiefendurchlaufs, so dass der Breitendurchlauf nicht mit Hilfe des Tiefendurchlaufs definiert werden kann.