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).

In diesem Kapitel werden wir uns anschauen, wie wir komplexe Strukturen, wie die eines Stammbaums, in Racket abbilden können und wie wir Funktionen zur Auswertung dieser nutzen können.

Aufgabe 1: Records der Spezies - Teil 1

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

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

(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 der mixed-Operator in der Signatur dient.

(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)

(d) Bestimme anhand deines in dieser Aufgabe gewonnenen Wissens, welche Ausgaben die untenstehenden REPL-Eingaben produzieren.

(: id (mixed natural unbekannt) -> (mixed natural unbekannt))
(define id
    (lambda (x)
     x))

> (id 12)
> (id unbekannt)
> (id unb)

Aufgabe 4: Records der Spezies - Teil 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 eine Spezies bestimmt, ob eine andere 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.