Rekursive Datenstrukturen
Übersicht
Natürliche Zahlen
Natürliche Zahlen umfassen alle positiven ganzen Zahlen inklusive der Null. Der dazugehörige Typ Nat
(für natürliche Zahlen) sei deklariert als:
data Nat = Zero | Succ Nat
|
Dieses erste Beispiel ist auch gleichzeitig die erste Deklaration eines rekursiven Datentyps in diesem Kapitel.
Die Definition besagt, dass Zero ein Wert von Nat ist. Succ n muss ein Wert von
Nat sein, immer wenn es ein n gibt, das Element aus Nat ist. Mit anderen Worten
hat der Konstruktor Succ (kurz für "Successor" = Nachfolger) den Typ Nat -> Nat.
Die folgenden Beispiele stehen für verschiedene Elemente aus Nat:
Zero, Succ Zero, Succ(Succ Zero)...
(0) (1) (2)...
|
Die Zahl "6" würde als Element von Nat wie folgt dargestellt werden:
Succ(Succ(Succ(Succ(Succ(Succ Zero)))))
|
Jede natürliche Zahl kann durch
Nat dargestellt werden. Allerdings sind auch
undefinierte Werte enthalten, die keine wohldefinierte natürliche Zahl darstellen, wie
,
Succ ,
Succ(Succ). Auf diesen Sachverhalt ist aber
in vorherigen Vorträgen schon eingegangen worden, und er soll auch erst später
(s. Kapitel partielle Zahlen)
weiter betrachtet werden.
Vorher werden exemplarisch die einfachen arithmetischen und Vergleichsoperationen für den Typ Nat vorgestellt.
Die Addition (+) wird wie folgt definiert:
(+) :: Nat -> Nat -> Nat
m + Zero = m
m + Succ n = Succ(m + n)
|
Die Definition ist rekursiv und definiert '+' durch Pattern-Matching auf dem zweiten Argument. Solange jedes Element aus Nat,
ausser den Undefinierten, entweder Zero ist oder der Form Succ n mit n als Element aus Nat entspricht, sind die beiden Muster
der Gleichungen disjunkt und decken alle Zahlen (ausser den Undefinierten) ab. Die beiden Gleichungen werden auch das Programm für (+) genannt.
Nun wird Zero + Succ(Succ Zero) wie folgt bewertet:
Zero + Succ(Succ Zero)
= {2. Gleichung '+'}
Succ(Zero + Succ Zero)
= {2. Gleichung '+'}
Succ(Succ(Zero + Zero))
= {1. Gleichung '+'}
Succ(Succ Zero)
|
Diese Berechnung zeigt, warum es unpraktikabler Vorschlag ist, natürliche Zahlen durch den Datentyp Nat einzuführen:
die Arithmetik wird dadurch einfach zu ineffizient. Besonders die Berechnung von m + n benötigt n + 1 Berechnungsschritte.
Jetzt wird die Definition der Addition benutzt, um die Multiplikation (*) zu definieren:
(*) :: Nat -> Nat -> Nat
m * Zero = Zero
m * Succ n = (m * n) + m
|
Die Definition der Multiplikation wird nun für die Definition der Exponential-Funktion (^) genutzt:
(^) :: Nat -> Nat -> Nat
m ^ Zero = Succ Zero
m ^ Succ n = (m ^ n) * m
|
Es lässt sich unschwer erkennen, dass die Definitionen von +, * und ^ sehr ähnlichen Mustern folgen. Später wird diskutiert,
wie diese Muster weiter genutzt werden können
(s. Kapitel zur fold-Funktion).
Mit der folgenden Instanz-Deklaration ist es möglich, Nat als Teil der Typklasse Eq zu definieren:
instance Eq Nat where
Zero == Zero = True
Zero == Succ n = False
Succ m == Zero = False
Succ m == Succ n = (m == n)
|
Dabei handelt es sich um eine rekursive Definition, die Pattern-Matching auf beide Argumente anwendet. Diese Instanz deklariert Nat als einen
Typ, der auf Gleichheit geprüft werden kann.
Ebenso kann Nat auch als Teil von Ord deklariert werden, um Vergleiche zu ermöglichen:
instance Ord Nat where
Zero < Zero = False
Zero < Succ n = True
Succ m < Zero = False
Succ m < Succ n = (m < n)
|
Als nächster Schritt wird beschrieben, wie Elemente aus Nat mittels einer Funktion showNat ausgegeben
werden können:
showNat :: Nat -> String
showNat Zero = "Zero"
showNat(Succ Zero) = "Succ Zero"
showNat(Succ(Succ n))= "Succ ("++ showNat(Succ n)++")"
|
Die Definition von
showNat benutzt die drei Muster
Zero, Succ Zero und
Succ(Succ n). Diese Muster
unterscheiden sich alle voneinander und decken zusammen den ganzen Bereich von
Nat ab, nur der undefinierte
Bereich
wird vernachlässigt.
In der Definition von
showNat sind deshalb drei Muster enthalten, da die ersten beiden natürlichen Zahlen ohne
Klammern dargestellt werden.
Alternativ kann Nat auch wie folgt deklariert werden:
data Nat = Zero | Succ Nat
deriving (Eq, Ord, Show)
|
Dies ist einfacher, denn mit dieser Deklaration wird
Nat automatisch Teil jeder der Typklassen
Eq, Ord und
Show.
Allerdings sollte überprüft werden, ob das so erzeugte Verhalten auch dem erwarteten Verhalten entspricht
(s. Beispiel: Rational).
Die vorherigen
Instanz-Deklarationen entfallen somit bzw. müssen unterlassen werden, da es sonst zu unzulässigen Überlappungen kommt.
Als Anmerkung sei gesagt, dass die Funktion show für Nat die selbe Funktion ergibt wie showNat. Wie später
zu sehen sein wird, sind alle Zahlentypen Instanzen von Show. Allerdings können nicht alle Zahlen z.B. mit (<) verglichen werden.
Die verbleibende arithmetische Funktion, die auf alle Zahlen angewendet werden kann, ist die Subtraktion (-).
(-) :: Nat -> Nat -> Nat
m - Zero = m
Succ m - Succ n = m - n
|
Diese Definition benutzt Mustererkennung auf beide Argumente. Zusammengenommen sind die Muster disjunkt, aber nicht erschöpfend.
Bei den natürlichen Zahlen ist die Subtraktion nämlich nur eine partielle Funktion. Folgendes Beispiel soll dies verdeutlichen:
Succ Zero - Succ(Succ Zero)
= {2. Gleichung '-'}
Zero - Succ Zero
= {case exhaustion}
|
Der Ausdruck 'case exhaustion' soll darauf hinweisen, dass es keine passende Gleichung gibt, deren Muster auf
Zero - Succ Zero passt.
Allgemeiner ist
m - n = , wenn
m < n ist.
Die partielle Natur der Subtraktion ist auch die primäre Motivation für die Einführung der
Integer, bei denen die
Subtraktion eine totale Operation ist.
Zum Abschluss noch zwei weitere Beispiele für das, was mit Nat programmiert werden kann:
Fakultät:
fact :: Nat -> Nat
fact Zero = Succ Zero
fact (Succ n) = Succ n * fact n
|
Fibonacci:
fib :: Nat -> Nat
fib Zero = Zero
fib (Succ Zero) = Succ Zero
fib (Succ(Succ n))= fib(Succ n) + fib n
|
Durch diese rekursive Fibonacci-Funktion ergibt sich für fib die Summe der vorausgehenden zwei Fibonacci-Zahlen: fib n + 2
= fib n + 1 + fib n.
Die Fibonacci-Folge beginnt mit den Elementen 0, 1, 1, 2, 3, 4, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377...
Im Gegensatz zur Berechnung der Fakultät bleibt der Sinn der Fibonacci-Funktion meist auf der Strecke. Um ihn zu erläutern, ist ein Sprung ins
Jahr 1202 erforderlich. Damals stellte sich Fibonacci die Frage: "Wieviele Kaninchenpaare stammen am Ende eines Jahres
von einem Kaninchenpaar ab, wenn jedes Paar jeden Monat ein neues Paar als Nachkommen hat, das selbst vom zweiten Monat an Nachkommen-Paare
gebiert?" [4] Die Antwort: fib 14 = 377.
[nach oben]
Partielle Zahlen
In diesem Unterkapitel wird nun vertiefend auf die bereits in vorhergehenden Vorträgen erwähnten
Spezialfälle eingegangen. Dabei handelt es sich um die Werte
undefined (undefiniert,
) und
infinity
(unendlich, ∞ ) der natürlichen Zahlen
Nat.
Undefined wird wie folgt dargestellt:
Alle diese Elemente sind unterschiedlich, und jedes ist ein Element von Nat. Dass es sie gibt, resultiert aus drei
Gegebenheiten:
- ist ein Element aus Nat, da jede Deklaration eines Datentyps letztlich einen Extrawert
für den undefinierten Wert dieses Typs enthält.
- Konstruktoren eines Datentyps werden als nicht-strikt angenommen und
- Succ n ist ein Element aus Nat, wenn n Element aus Nat ist.
Um den Wert undefined näher zu erläutern und den Unterschied zwischen den einzelnen Varianten zu
zeigen, sei undefined wie folgt definiert:
undefined :: Nat
undefined = undefined
|
Dann ergibt sich bei den Vergleichen:
Zahlen> Zero < undefined
{interrupted!}
Zahlen> Zero < Succ undefined
True
Zahlen> Succ Zero < Succ undefined
{interrupted!}
Zahlen> Succ Zero < Succ(Succ undefined)
True
|
Die Ergebnisse müssen nun so interpretiert werden, dass
der natürlichen Zahl entspricht, für die es
keine Information gibt.
Succ ist die natürliche Zahl, für die nur bekannt ist, dass sie grösser
als
Zero ist. Für
Succ(Succ ) ist nur bekannt, dass diese Zahl grösser ist als
Succ Zero,
usw.
Nun gibt es noch einen weiteren Wert im Bereich Nat, der noch nicht angesprochen wurde. Dabei geht es um die unendliche Zahl
infinity, die folgendes Verhalten zeigt:
Succ(Succ(Succ(Succ ...)))
|
Dieser Wert kann definiert werden als:
infinity :: Nat
infinity = Succ infinity
|
infinity unterscheidet sich von allen anderen Werten, da es die einzige Zahl x ist, für die
Succ m < x den Wahrheitswert True für alle endlichen Zahlen zurückgibt. Insofern ist
infinity das grösste Element aus Nat.
Wird nach dem Wert von infinity gefragt, so wird folgendes ausgegeben:
Zahlen> infinity
Succ(Succ(Succ(Succ(Succ{interrupted!}))))
|
Unter anderem gilt für den Wert
infinity, dass
infinity + n = infinity für alle Zahlen
n, aber die Gleichung
n + infinity = infinity nur für endliche Zahlen zutrifft. Das Kapitel
Induktion beschreibt, wie diese Gleichungen geprüft werden.
Zusammenfassend können die Werte aus dem Bereich Nat in drei Klassen aufgeteilt werden:
- Endliche Zahlen, die den wohldefinierten natürlichen Zahlen entsprechen.
- Partielle Zahlen wie , Succ usw. und
- die unendliche Zahl infinity.
Diese Klassifikation gilt für alle rekursiven Datentypen. Für alle gibt es endliche, partielle und unendliche Elemente. Auch wenn die
unendliche natürliche Zahl nur selten gebraucht wird, so ist sie bei anderen Datentypen weniger selten.