Rekursive Datenstrukturen

Stammbaum Homo Sapiens

In der Biologie ist es gängig, Stammbäume zu verwenden, um die evolutionären Beziehungen zwischen verschiedenen Spezies darzustellen und deren Abstammungslinien im Laufe der Zeit abzubilden.

Der folgende Stammbaum zeigt einen Ausschnitt aus einem hypothetischen Stammbaum der Evolution des Menschen und inkludiert einige wesentlichen Spezies, die im Laufe der menschlichen Evolution aufgetreten sind. Zur groben Angabe zeitlicher Informationen wird mit mya (million years ago) eine in der Evolution gängige Zeitskala genutzt. Der Stammbaum zeigt wichtige Entwicklungsschritte wie die Abspaltung der Gattung Homo von den frühen Vormenschen (ca. 2,5 mya), das Auftreten der evolutionären Seitenlinie der Gattung Paranthropus (ca. 3 mya) oder das erste Auftreten von Homo sapiens (vor ca. 300.000 Jahren).

Anhand von Stammbäumen lassen sich beispielsweise Fragestellungen beantworten wie: "Was war der letzte gemeinsame Vorfahre zweier Spezies?", "Ist eine Spezies ein Vorfahre einer anderen?" oder "Wie weit liegen Spezies evolutiv auseinander?". Diese Fragen lassen sich bei einem Blick auf den reduzierten obigen Stammbaum noch leicht beantworten. Bedenkt man jedoch, dass weltweit bereits etwa 1,8 Millionen Spezies wissenschaftlich erfasst sind (Quelle: Bundesamt für Naturschutz) und ein noch größerer Anteil noch nichteinmal erfasst wurde, ist eine automatisierte Verarbeitungen von Stammbäumen unerlässlich.

Bevor wir uns jedoch an die Verarbeitung von Stammbäumen mit Racket machen können, müssen wir zuerst eine grundlegende Frage beantworten: "Wie können wir Stammbäume in Racket darstellen, um die Arbeit mit diesen zu ermöglichen?"

Aufgabe 1: Records der Spezies - Teil 1/3

Eine einfache Möglichkeit, die einzelnen Spezies darzustellen, stellt die Nutzung von Records dar.

(a) Definiere den Record speciesA, so dass die untenstehenden Definitionen gelingen:

(define boises (make-speciesA "P. boises"))
(define aethiopicus (make-speciesA "P. aethiopicus"))
(define afarensis (make-speciesA "A. afarensis"))

(b) Bestimme, welche Informationen aus dem Stammbaum mit diesen Record-Definitionen berücksichtigt sind und welche nicht?

Aufgabe 2: Records der Spezies - Teil 2/3

Als zentrale Information eines Stammbaums sind insbesondere die Verwandtschaftsverhältnisse der einzelnen Spezies wichtig. Diese Informationen sind in unseren Records jedoch noch nicht enthalten.

(a) Unsere Record-Definition speciesA besitzt bisher lediglich ein Feld. Das zur Festlegung des Namens der Spezies. Zur Darstellung der Verwandtschaftsverhältnisse wollen wir noch ein weiteres Feld zur Record-Definition hinzufügen. Begründe, welches der folgenden Felder eine geeignete Ergänzung darstellt:

1. Ein Feld, das den Vorfahren der Spezies angibt
2. Ein Feld, das einen Nachfahren der Spezies angibt
3. Ein Feld, das den mya-Wert der Spezies angibt

(b) Unten findest du zwei Vorschläge zur Ergänzung deiner Record-Definition speciesA. Begründe, welches der beiden Felder dir am geeignetsten erscheint, um den Stammbaum darzustellen.

;Vorschlag 1:
(speciesA-ancestor speciesA)

;Vorschlag 2:
(speciesA-ancestor string)

(c) Ergänze das geeignete Feld in deiner Record-Definition und versuche anschließend, die Definitionen der Records afarensis, aethiopicus und boises (Aufgabe 1 (a)) an die neue Record-Definition anzupassen. Welche Probleme treten dabei auf?

(d) Mit den uns bekannten Mitteln können wir noch keine geeignete Definition des Records afarensis durchführen. Den Entwurfsgedanken unserer Records können wir jedoch bereits zusammenfassen. Wähle hierzu die Beschreibungen aus, die unseren Entwurf geeignet repräsentieren:

;Eine Spezies ist definiert durch:
;

;Ein Vorfahre ist entweder:
;

Aufgabe 3: Exkurs: Signaturen mit mixed und Records ohne Felder

Tatsächlich stellt unser in Aufgabe 2 erarbeiteter Entwurfsgedanke gleich zwei Unklarheiten dar. Betrachten wir einmal die Beschreibung eines Vorfahrens:

;Ein Vorfahre ist entweder:
;eine Spezies oder unbekannt

1. Wie stellen wir sicher, dass Daten entweder eine Spezies oder unbekannt sind, jedoch auf keinen Fall von einem anderen Datentyp?
2. Wie stellen wir den Daten des Typs unbekannt dar?

Diesen Fragen werden wir in dieser Aufgabe nachgehen.

1. Gemischte Signaturen

(a) Analysiere den untenstehenden Code und überlege, welche Ausgaben die untenstehenden REPL-Eingaben produzieren könnten. Überprüfe deine Vermutung.

(: wert ((mixed natural string) -> natural))
(define wert
    (lambda (w)
     (if [string? w]
         0
         (+ w 1))))

> (wert 12)
> (wert 1.5)
> (wert "zwei")

(b) Erkläre, wozu mixed in der Signatur dient.

2. Records ohne Felder

(c) Zwei spannende Eigenschaften von Record-Definitionen sind zum einen, dass diese auch ohne jedes Feld definiert werden können und zum anderen, dass man in die Definition direkt eine Prüffunktion integrieren kann. Im untenstehenden Code ist dies dargestellt. Analysiere diesen und überlege, welche Ausgaben die untenstehenden REPL-Eingaben produzieren könnten. Überprüfe deine Vermutung.

(define-record unbekannt
  make-unbekannt
  unbekannt?)

(define unb (make-unbekannt))

> (make-unbekannt)
> (unbekannt? (make-unbekannt))
> (unbekannt? "unbekannt")
> (unbekannt? unb)

Aufgabe 4: Records der Spezies - Teil 3/3

(a) Passe mit deinem Wissen aus Aufgabe 3 die Record-Definition speciesA an. Denke dabei an unseren Entwurfsgedanken aus Aufgabe 2:

;Eine Spezies ist definiert durch:
;einen Namen und einen Vorfahren

;Ein Vorfahre ist entweder:
;eine Spezies oder unbekannt

(b) Definiere die Records für afarensis, aethiopicus und boises.
Überprüfe deine Implementierungen mit folgenden REPL-Eingaben:

> (speciesA-ancestor afarensis)
;Erwartet: Record unbekannt
> (speciesA-ancestor aethiopicus)
;Erwartet: Record afarensis
> (speciesA-ancestor boises)
;Erwartet: Record aethiopicus (der wiederum Record afarensis enthält)

Aufgabe 5: Rekursive Verarbeitung der Spezies-Records

(a) Um die nachfolgenden Aufgaben für alle Spezies durchführen zu können, findest du hier die verbleibenden Definitionen. Übertrage diese in dein Programm.

(define robustus (make-speciesA "P. robustus" aethiopicus))
(define rudolfensis (make-speciesA "H. rudolfensis" afarensis))
(define ergaster (make-speciesA "H. ergaster" rudolfensis))
(define erectus (make-speciesA "H. erectus" ergaster))
(define heidelbergensis (make-speciesA "H. heidelbergensis" ergaster))
(define neanderthalensis (make-speciesA "H. neanderthalensis" heidelbergensis))
(define sapiens (make-speciesA "H. neanderthalensis" heidelbergensis))

(b) Schreibe eine Funktion vorfahre?, die für zwei übergebene Spezies bestimmt, ob die zweite übergebene Spezies ein Vorfahre der ersteren ist.

(c) Schreibe eine Funktion nächster-vorfahre?, die für zwei Spezies den nächsten gemeinsamen Vorfahren bestimmt. Ist kein gemeinsamer Vorfahre vorhanden, soll ein Record vom Typ unbekannt zurückgegeben werden.