Einführung
Du arbeitest an einem Projekt, um ein Zugplanungssystem für ein stark befahrenes Schienennetz zu entwickeln.
Du sollst einen Prototyp für die Zugstrecken im Planungssystem entwickeln. Jede Strecke besteht aus einer Abfolge von Bahnhöfen, an denen ein bestimmter Zug hält.
Anleitung
Dein Team hat beschlossen, jede Zugstrecke im Fahrplan durch eine doppelt verkettete Liste darzustellen.
Jeder Bahnhof entlang der Strecke des Zuges wird durch einen Knoten in der verketteten Liste dargestellt.
Du brauchst dir keine Gedanken über Ankunfts- und Abfahrtszeiten an den Bahnhöfen zu machen.
Jeder Bahnhof wird einfach durch eine Zahl dargestellt.
Strecken können erweitert werden, indem du Bahnhöfe am Anfang oder Ende einer Strecke hinzufügst.
Sie können auch verkürzt werden, indem du Bahnhöfe am Anfang oder Ende einer Strecke entfernst.
Manchmal wird ein Bahnhof geschlossen, und in diesem Fall muss er aus der Strecke entfernt werden, auch wenn er nicht am Anfang oder Ende der Strecke liegt.
Die Größe einer Strecke bemisst sich nicht danach, wie weit der Zug fährt, sondern danach, an wie vielen Bahnhöfen er hält.
Die verkettete Liste ist eine grundlegende Datenstruktur in der Informatik und wird oft bei der Implementierung anderer Datenstrukturen verwendet.
Wie der Name schon sagt, ist sie eine Liste von Knoten, die miteinander verknüpft sind.
Sie ist eine Liste von „Knoten“, wobei jeder Knoten mit seinem Nachbarn oder seinen Nachbarn verknüpft ist.
In einer einfach verketteten Liste ist jeder Knoten nur mit dem Knoten verknüpft, der auf ihn folgt.
In einer doppelt verketteten Liste ist jeder Knoten sowohl mit dem Knoten verknüpft, der vor ihm kommt, als auch mit dem Knoten, der nach ihm kommt.
Wenn du tiefer in verkettete Listen eintauchen möchtest, schau dir diesen Artikel an, der sie mit schönen Zeichnungen erklärt.
Zustandsbehaftete Datenstrukturen
In funktionalen Sprachen wie Lean sind die meisten Werte von vornherein unveränderlich.
Das bedeutet, dass Aktualisierungen meist dadurch entstehen, dass ein neuer Wert erzeugt wird.
Der alte und der neue Wert existieren beide nebeneinander und können referenziert und verwendet werden.
Es gibt jedoch viele Situationen, in denen ein zustandsbehafteter Wert gewünscht oder sogar notwendig ist.
Ein zustandsbehafteter Wert wird durch Mutation aktualisiert, wobei der alte Wert ersetzt wird, statt einen neuen zu erzeugen.
Nach einer Mutation ist nur noch der aktualisierte Wert zugänglich.
Beachte, dass Mutationen einige Garantien der Sprache brechen können.
Eine reine Funktion muss für dieselbe Menge an Eingabewerten immer dasselbe Ergebnis liefern. Wenn sich ein Eingabewert jedoch mit der Zeit ändern kann, kann die Funktion auch bei gleichen Argumenten unterschiedliche Ergebnisse liefern.
Ähnlich verhält es sich, wenn eine Funktion neben dem Rückgabewert auch externe Änderungen bewirken oder aus anderen Quellen als ihren Parametern lesen kann: Dann können zwei Aufrufe derselben Funktion unterschiedliche und manchmal unvorhersehbare Ergebnisse haben.
Um solches zustandsbehaftete Verhalten zu handhaben, verlangt Lean wie andere funktionale Sprachen, dass Funktionen mit Seiteneffekten in eine besondere Art von Struktur eingehüllt werden, die sie von reinen Funktionen unterscheidet.
Diese Strukturen heißen Monaden.
Wichtig ist: Obwohl jeder zustandsbehaftete Wert in einer Monade mit Seiteneffekten lebt, stellt nicht jede Monade veränderlichen Zustand dar.
Bekannte Beispiele für „reine“ Monaden sind Option, Except und Id.
In dieser Übung definierst du eine zustandsbehaftete Datenstruktur namens LinkedList.
Instanzen dieser Datenstruktur werden durch Mutation aktualisiert.
Um das zu ermöglichen, sind alle Funktionen in die ST-Monade eingehüllt.
In dieser Monade ist veränderlicher Zustand der einzige Seiteneffekt, und veränderliche Referenzen können nicht entkommen.
Weitere Informationen findest du in der Referenz.
Quelle
Klassisches Thema der Informatik
