Wir beschäftigen uns weiter mit induktiven Datentypen und mit rekursiver Programmierung,

letztendlich via Folds, also via initiale Algebraeigenschaft.

Was wir heute vor allem tun wollen, ist die Ausdrucksstärke des bisher eingeführten

Formalismus etwas verstärken. Der bisherige Formalismus war ja durchaus so ein bisschen

langweilig, sagen wir mal. Der erlaubte uns, Datentypen zu definieren, deren Semantik letztlich

bestand aus lauter geschlossenen Termen, das heißt, ich habe in diesen Datentypen praktisch

Konstanten und ich habe Konstruktoren, die mir erlauben, aus diesen Konstanten kompliziertere

Sachen zu machen, schon wenn ich versuche damit einen Datentyp von Listen zu bauen, scheitere

ich jedenfalls dann, wenn der generisch sein soll, weil ich einfach keine Möglichkeit habe,

Werte von irgendwo zu importieren. Ich möchte ja normalerweise einen Listenkonstruktor haben,

also einen Typkonstruktor für Listen, der einen beliebig vorgegebenen Typ von Zahlen,

anderen Listen, Bäumen, sonst was als Argument nimmt und dann darüber einen Datentyp von

Listen baut. Und genau das werden wir uns heute ansehen, also sprich, wie man das in den Formalismus integriert.

So, der Schlüssel dabei ist zu mehrsortigen Signaturen überzugehen, das ist also etwas,

was wir bisher noch nicht gesehen haben. Die bisherigen Signaturen, die wir verwendet haben,

waren ja einfach die, wie wir sie aus Gleuen kannten, das heißt, es gibt letztlich nur

einen globalen Typ, das Universum und alle Operationen arbeiten auf diesen globalen Typ.

Und das wollen wir jetzt so ein bisschen ausdifferenzieren. Und zwar fangen wir an mit einem Beispiel.

Ja, eine Sache habe ich eben schon angedeutet. Wir wollen eigentlich sowas haben wie Parametersorten,

die wir also importieren und aus denen wir komplexere Datentypen bauen. Wir haben schon einen Datentyp A

und bauen daraus einen Datentyp Listen von A. Und dann haben wir hinterher natürlich zwei Sorten.

Wir haben das A, das wir schon hatten, und wir haben die Listen. Wenn wir schon dabei sind,

dann verallgemeinern wir das jetzt aber gleich dahin, dass wir nicht nur einen Datentyp neu einführen,

sondern womöglich mehrere, die dann gegenseitig aufeinander Bezug nehmen.

So, ein ganz häufig verwendeter Datentyp von dieser Art ist der folgende.

Ich führe mal wieder ein, ein Datentyp von Bäumen, um das jetzt nicht zu verbos zu machen,

und dann lassen die Dinger wieder Bäume, also Tree. Die sind aber anders, als wir sie bisher gesehen haben.

Und zwar werden die anders sein, indem wir den Verzweigungsgrad nicht festlegen.

Wir haben ja schon gesehen, binäre Bäume, wo also der Verzweigungsgrad sehr stark eingeschränkt ist.

Ein gegebener Knoten und ein Binärbaum in unserem Sinne hat entweder gar keine Kinder oder genau zwei.

Und man kann sich natürlich beliebig verallgemeinerte Verzweigungsgrade vorstellen.

Wir können jetzt einen Datentyp von Bäumen einführen, wo wir nur noch verlangen, dass der Verzweigungsgrad endlich ist.

Wir verlangen nicht, dass er überall derselbe ist und wir wollen ihn auch nicht nach oben beschränken.

Ja, was heißt denn das also? Das heißt, naja, wenn ich mir davon mal ein Bild male,

hier habe ich so einen Knoten in so einem Baum, der hat also irgendeine Anzahl Kinder.

So, und die Kinder sind wieder Bäume.

Letztlich, weil nicht gesagt ist, wie viele das sind, haben wir hier also einfach eine Liste von Kindern,

so wie man sich seine Kinder auch normalerweise vorstellt.

Und naja, was ist eine Liste von Bäumen?

Eine Liste von Bäumen ist natürlich ein Wald.

Ja, und dann brauchen wir Konstruktoren für diese beiden Datentypen.

Ja, einmal das vielleicht am wenigsten Überraschende.

Wir haben wieder so einen Konstruktor für Blätter von Bäumen.

Wie wir das beim letzten Mal schon gesehen haben, da ändert sich auch nichts.

Wir wollen nun die Labels in diesem Falle gerade an die Blätter wieder schreiben,

also innere Knoten wollen wir nicht labeln. Wir haben nur also den eigentlichen Inhalt des Baumes,

den haben wir nur hier unten an den Blättern stehen.

Und wir haben also wieder einen Konstruktor, der uns aus einem einzelnen Datenwert vom Typ A ein Blatt macht,

was dann für sich genommen schon ein Baum ist.

Und dann haben wir wieder unseren Knoten-Konstruktor.