Rekursiver Datentyp – Wikipedia

Datentyp, der sich in seiner Definition auf sich selbst bezieht

In Computerprogrammiersprachen, a rekursiver Datentyp (auch bekannt als a rekursiv definiert, induktiv definiert oder induktiver Datentyp) ist ein Datentyp für Werte, die andere Werte desselben Typs enthalten können. Daten rekursiver Typen werden normalerweise als gerichtete Graphen betrachtet.

Eine wichtige Anwendung der Rekursion in der Informatik ist die Definition dynamischer Datenstrukturen wie Listen und Bäume. Rekursive Datenstrukturen können als Reaktion auf Laufzeitanforderungen dynamisch auf eine beliebig große Größe anwachsen; Im Gegensatz dazu müssen die Größenanforderungen eines statischen Arrays zur Kompilierzeit festgelegt werden.

Manchmal wird der Begriff “induktiver Datentyp” für algebraische Datentypen verwendet, die nicht unbedingt rekursiv sind.

Beispiel[edit]

Ein Beispiel ist der Listentyp in Haskell:

data List a = Nil | Cons a (List a)

Dies zeigt an, dass eine Liste von a’s entweder eine leere Liste oder a . ist Nachteile Zelle mit einem ‘a’ (dem “Kopf” der Liste) und einer weiteren Liste (dem “Ende”).

Ein weiteres Beispiel ist ein ähnlicher einfach verlinkter Typ in Java:

class List<E> {
    E value;
    List<E> next;
}

Dies zeigt an, dass eine nicht leere Liste des Typs E einen Datenmember des Typs E und einen Verweis auf ein anderes List-Objekt für den Rest der Liste enthält (oder einen Null-Verweis, um anzuzeigen, dass dies das Ende der Liste ist).

Gegenseitig rekursive Datentypen[edit]

Datentypen können auch durch gegenseitige Rekursion definiert werden. Das wichtigste grundlegende Beispiel hierfür ist ein Baum, der sich gegenseitig rekursiv im Sinne eines Waldes (einer Baumliste) definieren lässt. Symbolisch:

f: [t[1], ..., t[k]]
t: v f

Ein Wald F besteht aus einer Liste von Bäumen, während ein Baum T besteht aus einem Wertpaar v und ein Wald F (seine Kinder). Diese Definition ist elegant und abstrakt leicht zu handhaben (z. B. beim Beweis von Sätzen über Eigenschaften von Bäumen), da sie einen Baum in einfachen Worten ausdrückt: eine Liste eines Typs und ein Paar von zwei Typen.

Diese gegenseitig rekursive Definition kann in eine einfach rekursive Definition umgewandelt werden, indem die Definition einer Gesamtstruktur eingefügt wird:

t: v [t[1], ..., t[k]]

Ein Baum T besteht aus einem Wertpaar v und eine Liste von Bäumen (seine Kinder). Diese Definition ist kompakter, aber etwas unübersichtlicher: Ein Baum besteht aus einem Paar eines Typs und einer Liste eines anderen, die entwirrt werden müssen, um Ergebnisse zu beweisen.

In Standard ML können die Datentypen Baum und Gesamtstruktur wie folgt gegenseitig rekursiv definiert werden, was leere Bäume ermöglicht:

datatype 'a tree = Empty | Node of 'a * 'a forest
and      'a forest = Nil | Cons of 'a tree * 'a forest

In Haskell können die Baum- und Walddatentypen ähnlich definiert werden:

data Tree a = Empty
            | Node (a, Forest a)

data Forest a = Nil
              | Cons (Tree a) (Forest a)

In der Typentheorie hat ein rekursiver Typ die allgemeine Form μα.T, wobei die Typvariable α im Typ T vorkommen kann und für den gesamten Typ selbst steht.

Zum Beispiel können die natürlichen Zahlen (siehe Peano-Arithmetik) durch den Haskell-Datentyp definiert werden:

data Nat = Zero | Succ Nat

In der Typentheorie würden wir sagen:

wobei die beiden Arme des Summentyps die Datenkonstruktoren Zero und Succ darstellen. Zero nimmt keine Argumente an (also repräsentiert durch den Einheitentyp) und Succ nimmt ein anderes Nat (also ein weiteres Element von

).

Es gibt zwei Formen rekursiver Typen: die sogenannten isorekursiven Typen und die equirekursiven Typen. Die beiden Formen unterscheiden sich darin, wie Terme eines rekursiven Typs eingeführt und eliminiert werden.

Isorekursive Typen[edit]

Bei isorekursiven Typen ist der rekursive Typ

und seine Erweiterung (oder abrollen)

(Wo die Notation

gibt an, dass alle Instanzen von Z in X durch Y ersetzt werden) unterschiedliche (und disjunkte) Typen mit speziellen Termkonstrukten sind, die normalerweise als bezeichnet werden rollen und abrollen, die einen Isomorphismus zwischen ihnen bilden. Um genau zu sein:

und

, und diese beiden sind Umkehrfunktionen.

Äquikursive Typen[edit]

Unter equirecursive Regeln ist ein rekursiver Typ

und sein Abrollen

sind gleich — das heißt, diese beiden Typausdrücke bezeichnen denselben Typ. Tatsächlich gehen die meisten Theorien von equirecursiven Typen weiter und spezifizieren im Wesentlichen, dass zwei beliebige Typenausdrücke mit derselben “unendlichen Erweiterung” äquivalent sind. Als Ergebnis dieser Regeln tragen equirecursive Typen wesentlich mehr Komplexität zu einem Typsystem bei als isorekursive Typen. Algorithmische Probleme wie Typprüfung und Typinferenz sind auch für equirecursive Typen schwieriger. Da ein direkter Vergleich auf einem äquirekursiven Typ keinen Sinn macht, können sie in O(n log n)-Zeit in eine kanonische Form umgewandelt werden, die leicht verglichen werden kann.^[2]

Equirecursive Typen erfassen die Form von selbstreferentiellen (oder gegenseitig referenziellen) Typdefinitionen, die in prozeduralen und objektorientierten Programmiersprachen zu sehen sind, und treten auch in der typtheoretischen Semantik von Objekten und Klassen auf. In funktionalen Programmiersprachen sind isorekursive Typen (in Form von Datentypen) weitaus häufiger.

Typisch synonym[edit]

Rekursion ist in Typsynonymen in Miranda, OCaml nicht erlaubt (es sei denn, -rectypes Flag verwendet wird oder es sich um einen Datensatz oder eine Variante handelt) und Haskell; So sind beispielsweise die folgenden Haskell-Typen illegal:

type Bad = (Int, Bad)
type Evil = Bool -> Evil

Stattdessen muss es in einen algebraischen Datentyp eingeschlossen werden (auch wenn es nur einen Konstruktor hat):

data Good = Pair Int Good
data Fine = Fun (Bool -> Fine)

Dies liegt daran, dass Typsynonyme, wie typedefs in C, zur Kompilierzeit durch ihre Definition ersetzt werden. (Typsynonyme sind keine “echten” Typen; sie sind nur “Aliasnamen” für den Programmierer.) Aber wenn dies mit einem rekursiven Typ versucht wird, wird es endlos wiederholt, denn egal wie oft der Alias ​​ersetzt wird, er bleibt trotzdem bezieht sich auf sich selbst, zB “Bad” wächst auf unbestimmte Zeit: Bad → (Int, Bad) → (Int, (Int, Bad)) → ... .

Eine andere Möglichkeit besteht darin, dass eine Indirektionsebene (der algebraische Datentyp) erforderlich ist, damit das isorekursive Typsystem herausfinden kann, wann es rollen und abrollen.

Siehe auch[edit]

Dieser Artikel basiert auf Material aus dem Kostenloses Online-Wörterbuch der Informatik vor dem 1. November 2008 und unter den “Neulizenzierungs”-Bedingungen der GFDL, Version 1.3 oder höher, enthalten.