Dieser Audiobeitrag wird von der Universität Erlangen-Nürnberg präsentiert.

Ja, herzlich willkommen. Wir hatten ja die letzte Sitzung damit abgeschlossen, dass wir uns Gedanken

gemacht haben zum Thema, wie modellieren wir einen Typ unverzweigender Bäume, dafür gibt es

einen Fachausdruck, die sogenannten Rose Trees, wie modellieren wir die als Datentyp? Und wir haben

festgestellt, gut, in dieser einsortigen Welt, die wir bisher kennengelernt haben, wird das schwierig,

sagen wir mal zumindest. Wir haben uns nicht direkt einen Möglichkeitbeweis geführt, aber wir sind auf

keine Lösung gekommen. Und es hat sich dann bei den Gedanken, die wir uns gemacht haben, schon angedeutet,

dass man wohl zwei Typen braucht, und zwar einen Typ von Bäumen und einen Typ von beliebig vielen

nebeneinander stehenden Bäumen, sprich Listen von Bäumen oder eben Wäldern. So, und ja, das machen wir

jetzt mal formal. Also befassen wir uns jetzt mit mehrsortigen Datentypen. Wir beginnen das mal damit,

dass wir unser Eingangsbeispiel, das mit den Rose Trees, jetzt mal ausformulieren. So, wir erweitern

ein bisschen unsere Privatsyntax, die wir hier verwenden, um Datentypen zu deklarieren. Wir

behalten bei unser Schlüsselwort Data, aber wir ändern das ab. Da wo vorher also nur ein Datentyp

kommt, dürfen jetzt mehrere kommen. Sagen wir einerseits Tree A, also Bäume, soll heißen mit

Blättern gelabelt in A und Forest A, also Wälder bestehend aus eben solchen Bäumen. So, nach dem

Wire folgen jetzt also unsere Konstruktoren für diese beiden Datentypen. Wir hatten das nun schon

so formuliert, dass also wir jetzt die Syntax für diese Konstruktoren praktisch kaum noch ändern

müssen. Wir hatten ja zwar für eine Signatur gesagt, okay, wir geben pro Symbol einfach nur

die Stelligkeit an, aber in diesen Datentyp-Deklarationen hatten wir schon immer explizite

Typen geschrieben und das machen wir jetzt einfach auch weiter. Also, einmal machen wir

Konstruktoren für Bäume. Also Bäume sollen, wie gesagt, Einträge aus A an den Blättern stehen

haben. Die Knoten sollen leer sein, die sollen nur der Verzweigung dienen. Das heißt, wir haben

einen Konstruktor Blatt. Da schreibe ich halt einen so einen Eintrag aus A ran und das gibt mir dann

ein Blatt. Also, Leaf ist ein Konstruktor von A nach Tree A. Die andere Möglichkeit, was ein Baum

sein kann aus einem Blatt ist eben eine Verzweigung und zwar eine beliebig breite Verzweigung mit

anderen Worten. Das, was entsteht, wenn ich von einem so verzweigenden Baum hier oben die Wurzel

wegnehme, ist ein Wald. Den Konstruktor nenne ich mal Node. Jetzt von dieser Baummetapher dann an der Stelle vielleicht mal ein bisschen abweichend.

Und in den Konstruktor stecke ich also rein einen Forest, also die Zweige, die drunter kommen und ich

bekomme einen Baum raus. Soweit so gut, aber jetzt müssen wir natürlich noch sagen, wie wir diese

Forests konstruieren. Gut, die Forests sollen schlicht und einfach Listen von Bäumen sein. Das

heißt, die Konstruktoren dafür, die kann ich mir jetzt praktisch abschreiben, nur dass jetzt dieser

Typ der Trees mit in den Typ reinfließt. Also, Liste heißt, ich habe eine Leere Liste, Nö. Die ist ein Forest, der leere

Wald. Der andere typische Listenkonstruktor ist Kons. Da packe ich rein einen neuen Baum im Wald und den alten Wald und

kriege einen neuen größeren Wald raus. So, das ist die Datentyp-Deklaration. So, was wir jetzt nicht gemacht haben, was

letztes Mal vorgeschlagen worden war, war ja jetzt da eine geschachtete Datentyp-Definition zu machen.

Also, wir statt Bäumen, statt Wäldern einfach explizit von Listen von Bäumen reden, was auch viele

Vorteile hat, besonders dann, wenn man für Listen schon ein bisschen was programmiert hat. So, hier

implementieren wir das ja gerade nicht wirklich. Das heißt, wir tun mal einfach so als ob. Das heißt,

wir verwechseln jetzt einfach mal großzügig Forest A mit List von Tree A. Ja, das heißt, was soll das

heißen? Das heißt, wir verwenden unsere ganze Listennotation, die wir jetzt schon kennen,

zum Beispiel einer Liste oder Listenkonkatenation oder alles mögliche, was wir für Listen halt schon

kennen. Das verwenden wir jetzt einfach sang und klanglos auch für Bäume, eigentlich für Bäume,

für Wälder. So, was wir jetzt machen wollen ist als nächstes, ne, wollen wir nicht. Also, kommt

das ein bisschen später. Also, was wir jetzt tun ist, das, was wir hier am Beispiel sehen, in

eine formale Definition zu gießen. Die formale Definition wird etwas ungemütlicher als die

vorige, weil wir einfach mit mehr Daten zu kämpfen hatten, wo wir vorher nur eine Sorte hatten, die

wir nicht weiter benannt haben und bei Operationen nur von Stelligkeit reden mussten. Da müssen wir

jetzt eben überall über diese Sorten reden. Das heißt, wir müssen praktisch ein relativ

leichtgewichtiges Typsystem noch mal einführen. Das machen wir jetzt, müssen wir durch.

Ja, also allgemein, was passiert hat? Wir haben ja schon im Fall der einsortigen Datentypen gesehen,