Strukturierung: Rekursive Datenstrukturen

Rekursive Datenstrukturen

In vielen Fällen ist es wichtig, die Beziehungen zwischen einzelnen Daten abbilden zu können, beispielsweise bei den verschiedenen Spezies in einem Stammbaum. Um dies zu ermöglichen, nutzen wir spezielle Strukturen zur Darstellung der Daten: Rekursive Datenstrukturen.

So beinhaltet beispielsweise unsere Record-Definition speciesA sich selbst als Datentyp für das Feld speciesA-ancestor.

(define-record speciesA
  make-speciesA
  (speciesA-name string)
  (speciesA-ancestor (mixed speciesA unbekannt)))

Der Selbstverweis einer rekursiven Datenstruktur kann jedoch problematisch werden, wenn Daten vom Typ der Datenstruktur keine entsprechenden Daten haben, auf die diese verweisen können. In unserem Beispiel entsprach dies dem ersten Eintrag des Stammbaums A. afarensis, für den kein Vorfahre im Baum existiert. Wir brauchen daher ein Element, welches wir an diesen Stellen referenzieren können. Wir nennen dies den Basisfall einer rekursiven Datenstruktur.

Für die Record-Definition speciesA definieren wir als Basisfall die Record-Definition unbekannt. Um in Racket anzugeben, dass Daten verschiedener Datentypen akzeptiert werden, nutzen wir den Operator mixed.

(define-record unbekannt
  make-unbekannt
  unbekannt?)

(define-record speciesA
  make-speciesA
  (speciesA-name string)
  (speciesA-ancestor (mixed speciesA unbekannt)))

Aufgabe 1: Spezies als Baumstruktur

Mit unseren Definitionen der Records vom Typ speciesA haben wir bereits sämtliche Namen und Verbindungen zwischen den einzelnen Spezies des Stammbaums abgebildet. Einige Fragestellungen lassen sich anhand der Definitionen bisher jedoch nicht automatisiert beantworten.

Angenommen, wir möchten Funktionen schreiben, die die folgenden Fragestellungen beantworten:

1. Wie viele Elemente hat der Stammbaum?
2. Ist eine Spezies Teil des Stammbaums?
3. Wie viele Nachkommen stammen von einer Spezies ab?

(a) Erkläre, warum diese Fragestellungen in unserer bisherigen Record-Struktur nicht beantwortbar sind und überlege dir, welche Infos die Records beinhalten müssten, um diese Fragen beantwortbar zu machen.

Eine alternative und in der Praxis gängige Möglichkeit, den Stammbaum zu repräsentieren, ist die Nutzung einer rekursiven Baumstruktur. Ein großer Vorteil hier ist unter anderem, dass wir auch nicht mehr für jede Spezies eine einzelne Definition schreiben müssen.

(b) Analysiere den Aufbau der Definition speciestree und schreibe anschließend eine Record-Definition speciesB, die eine entsprechende Darstellung des Stammbaums ermöglicht.

(define speciestree
  (make-speciesB "A. afarensis"
                 (make-speciesB "H. rudolfensis"
                                (make-speciesB "H. ergaster"
                                               (make-speciesB "H. heidelbergensis"
                                                              (make-speciesB "H. neanderthalensis" unb unb)
                                                              (make-speciesB "H. sapiens" unb unb))
                                               (make-speciesB "H. erectus" unb unb))
                                unb)
                 (make-speciesB "P. aethiopicus"
                                (make-speciesB "P. robustus" unb unb)
                                (make-speciesB "P. boises" unb unb))))

Aufgabe 2: Rekursive Verarbeitung der Spezies-Baumstruktur

(a) Schreibe eine Funktion elemente-in-baum, die für einen übergebenen Baum mit Records des Typs SpeciesB die Anzahl aller Elemente im Baum bestimmt.

(b) Schreibe eine Funktion get-elem, die dir für einen übergebenen Speziesnamen den Record der Spezies aus dem Baum zurückliefert.

(c) Schreibe eine Funktion anzahl-nachkommen, die für eine Spezies bestimmt, wie viele Nachkommen diese im Baum aufweist.