In imperativen Sprachen ist es üblich, dass Datenstrukturen wie Arrays durch destruktive Operationen wie Schreibzugriffe unwiderrufbar verändert werden. Idiomatischer Code in Haskell nutzt dagegen oft \emph{persistente} Datenstrukturen, da destruktive Operationen nicht mit der call-by-need Auswertungsreihenfolge harmonieren. Solche Datenstrukturen basieren meistens auf Bäumen. Operationen, die die repräsentierten Daten verändern, liefern meistens eine Kopie zurück, die sich mit der vorherigen Version der Datenstruktur den Großteil des Speichers teilt.

Ein großer Vorteil persistenter Datenstrukturen: Das Klonen einer solchen ist ein no-op, da keine Operation frühere Versionen verändern kann. Ein Nachteil: Wird zu jedem Zeitpunkt nur die aktuellste Version der Datenstruktur benötigt, sind die Kopien unnötig und der entstehende Müll belastet den Garbage Collector.

Transiente Datenstrukturen versuchen die Vorteile von persistenten Datenstrukturen und destruktiven Datenstrukturen zu verbinden, indem je nach Bedarf Zugriff auf eine persistente Ansicht oder eine destruktive, \emph{ephemere} Ansicht der Datenstruktur gewährt wird. Für nützliche transiente Paarungen geschieht der Wechsel zwischen beiden Ansichten in amortisiert konstanter Zeit.

Aufgabe:

Die Aufgabe in dieser Bachelorarbeit war es, eine erste funktionierende Bibliothek für transiente Datenstrukturen in Haskell bereitzustellen und im Rahmen einer Fallstudie die Anwendbarkeit und die Auswirkungen auf Performance im Glasgow Haskell Compiler (GHC) auszuwerten.

Voraussetzungen

Haskell Kenntnisse

Schlüsselworte

Haskell, Datenstrukturen, Transients 

Veröffentlichungen

Veröffentlichung

Transient Data Structures for Haskell

Betreuer

Wissenschaftliche Mitarbeiter
Sebastian Graf

Studenten

Ehemalige Studenten
Pascal Ellinger