In der Informatik ist eine rein funktionale Datenstruktur eine Datenstruktur , die direkt in einer rein funktionalen Programmiersprache implementiert werden kann . Der Hauptunterschied zwischen einer beliebigen und einer rein funktionalen Datenstruktur besteht darin, dass letztere (stark) unveränderlich ist . Diese Einschränkung gewährleistet, dass die Datenstruktur die Vorteile unveränderlicher Objekte besitzt: (vollständige) Persistenz , schnelles Kopieren von Objekten und Thread-Sicherheit . Effiziente rein funktionale Datenstrukturen können die Verwendung von verzögerter Auswertung und Memoisation erfordern .

Definition

Persistente Datenstrukturen besitzen die Eigenschaft, frühere Versionen unverändert zu speichern. Nicht-persistente Strukturen wie Arrays hingegen erlauben destruktive Aktualisierungen [ 1 ] , d. h. Aktualisierungen, die nicht rückgängig gemacht werden können. Sobald ein Programm einen Wert an einer bestimmten Stelle des Arrays speichert, kann dessen vorheriger Wert nicht mehr abgerufen werden.

Formal gesehen ist eine rein funktionale Datenstruktur eine Datenstruktur, die in einer rein funktionalen Sprache wie Haskell implementiert werden kann . In der Praxis bedeutet dies, dass die Datenstrukturen ausschließlich aus persistenten Datenstrukturen wie Tupeln, Summentypen , Produkttypen und Basistypen wie Ganzzahlen, Zeichen und Zeichenketten bestehen müssen. Eine solche Datenstruktur ist notwendigerweise persistent. Allerdings sind nicht alle persistenten Datenstrukturen rein funktional. [ 1 ] : 16 Beispielsweise ist ein persistentes Array eine Datenstruktur, die persistent ist und mithilfe eines Arrays implementiert wird; sie ist daher nicht rein funktional.

In seinem Buch „Purely functional data structures“ vergleicht Okasaki destruktive Aktualisierungen mit den Messern eines Meisterkochs. [ 1 ] : 2 Destruktive Aktualisierungen sind unumkehrbar und sollten daher nur verwendet werden, wenn sicher ist, dass der vorherige Wert nicht mehr benötigt wird. Destruktive Aktualisierungen ermöglichen jedoch auch eine Effizienzsteigerung, die mit anderen Techniken nicht zu erreichen ist. Beispielsweise kann eine Datenstruktur, die ein Array und destruktive Aktualisierungen verwendet, durch eine ähnliche Datenstruktur ersetzt werden, bei der das Array durch eine Map , eine Random-Access-Liste oder einen balancierten Baum ersetzt wird , was eine rein funktionale Implementierung zulässt. Die Zugriffskosten können sich jedoch von konstanter auf logarithmische Zeit erhöhen .

Sicherstellen, dass eine Datenstruktur rein funktional ist

Eine Datenstruktur ist niemals inhärent funktional. Beispielsweise kann ein Stack als einfach verkettete Liste implementiert werden . Diese Implementierung ist rein funktional, solange die einzigen Operationen auf dem Stack einen neuen Stack zurückgeben, ohne den alten zu verändern. Ist die Sprache jedoch nicht rein funktional, kann das Laufzeitsystem die Unveränderlichkeit möglicherweise nicht garantieren. Dies veranschaulicht Okasaki [ 1 ] : 9–11, wo er zeigt, dass die Verkettung zweier einfach verketteter Listen auch im imperativen Kontext möglich ist.

Um sicherzustellen, dass eine Datenstruktur in einer nicht rein funktionalen Sprache rein funktional verwendet wird, können Module oder Klassen verwendet werden, um die Manipulation ausschließlich über autorisierte Funktionen zu gewährleisten.

Verwendung rein funktionaler Datenstrukturen

Eine der zentralen Herausforderungen bei der Anpassung bestehenden Codes an die Verwendung rein funktionaler Datenstrukturen besteht darin, dass veränderliche Datenstrukturen „versteckte Ausgaben“ für die sie verwendenden Funktionen liefern. Um diese Funktionen so umzuschreiben, dass sie rein funktionale Datenstrukturen verwenden, müssen diese Datenstrukturen als explizite Ausgaben hinzugefügt werden.

Betrachten wir beispielsweise eine Funktion, die eine veränderliche Liste entgegennimmt, das erste Element entfernt und dieses Element zurückgibt. In einem rein funktionalen Kontext erzeugt das Entfernen eines Elements aus der Liste eine neue, kürzere Liste, aktualisiert aber nicht die ursprüngliche. Um also sinnvoll zu sein, muss eine rein funktionale Version dieser Funktion wahrscheinlich die neue Liste zusammen mit dem entfernten Element zurückgeben. Im allgemeinsten Fall muss ein so umgewandeltes Programm bei jedem Funktionsaufruf den „Zustand“ oder „Speicher“ des Programms als zusätzliches Ergebnis zurückgeben. Ein solches Programm wird als im Store-Passing-Stil geschrieben bezeichnet .

Beispiele

Hier ist eine Liste abstrakter Datenstrukturen mit rein funktionalen Implementierungen:

Entwurf und Umsetzung

In seinem Buch „Purely Functional Data Structures“ beschreibt der Informatiker Chris Okasaki Techniken zur Entwicklung und Implementierung rein funktionaler Datenstrukturen, von denen eine kleine Auswahl im Folgenden zusammengefasst wird.

Faulheit und Auswendiglernen

Die verzögerte Auswertung ist in rein funktionalen Sprachen besonders interessant [ 1 ] : 31, da die Reihenfolge der Auswertung das Ergebnis einer Funktion niemals beeinflusst. Daher wird die verzögerte Auswertung auf natürliche Weise zu einem wichtigen Bestandteil der Konstruktion rein funktionaler Datenstrukturen. Sie ermöglicht es, eine Berechnung erst dann durchzuführen, wenn ihr Ergebnis tatsächlich benötigt wird. Somit kann der Code einer rein funktionalen Datenstruktur ohne Effizienzverlust Daten, die tatsächlich verwendet werden, und Daten, die ignoriert werden, gleichermaßen behandeln. Die einzige notwendige Berechnung betrifft die Daten der ersten Kategorie; nur diese Daten werden tatsächlich verarbeitet.

Eine der wichtigsten Methoden zum Aufbau effizienter, rein funktionaler Datenstrukturen ist die Memoisation. [ 1 ] : 31 Sobald eine Berechnung abgeschlossen ist, wird sie gespeichert und muss nicht erneut durchgeführt werden. Dies ist besonders wichtig bei verzögerten Auswertungen; zusätzliche Auswertungen können dasselbe Ergebnis erfordern, aber es ist unmöglich vorherzusagen, welche Auswertung es zuerst benötigt.

Amortisationsanalyse und Terminplanung

Manche Datenstrukturen, selbst solche, die nicht rein funktional sind, wie z. B. dynamische Arrays , erlauben Operationen, die meist effizient (z. B. konstante Laufzeit für dynamische Arrays) und selten ineffizient (z. B. lineare Laufzeit für dynamische Arrays) sind. Mithilfe der Amortisation lässt sich dann beweisen, dass die durchschnittliche Laufzeit der Operationen effizient ist. [ 1 ] : 39 Das heißt, die wenigen ineffizienten Operationen sind so selten, dass sie die asymptotische Entwicklung der Zeitkomplexität bei Betrachtung einer Operationsfolge nicht verändern.

Generell sind ineffiziente Operationen für persistente Datenstrukturen nicht akzeptabel, da diese Operationen mehrfach aufgerufen werden können. Auch für Echtzeit- und imperative Systeme, bei denen die Ausführungszeit der Operation vorhersehbar sein muss, ist dies nicht akzeptabel. Darüber hinaus erschwert diese Unvorhersehbarkeit die Nutzung von Parallelverarbeitung . [ 1 ] : 83

Um diese Probleme zu vermeiden, ermöglichen manche Datenstrukturen das Aufschieben ineffizienter Operationen – dies wird als Scheduling bezeichnet . [ 1 ] : 84 Die einzige Voraussetzung ist, dass die Berechnung der ineffizienten Operation abgeschlossen sein muss, bevor ihr Ergebnis benötigt wird. Ein konstanter Teil der ineffizienten Operation wird gleichzeitig mit dem nachfolgenden Aufruf einer effizienten Operation ausgeführt, sodass die ineffiziente Operation bereits vollständig abgeschlossen ist, wenn sie benötigt wird, und jede einzelne Operation effizient bleibt.

Beispiel: Warteschlange

Amortisierte Warteschlangen [ 1 ] : 65 [ 1 ] : 73 bestehen aus zwei einfach verketteten Listen: der vorderen und der umgekehrten hinteren Liste. Elemente werden der hinteren Liste hinzugefügt und aus der vorderen Liste entfernt. Ist die vordere Warteschlange leer, wird die hintere Liste umgekehrt und zur vorderen, während die hintere Warteschlange leer wird. Die amortisierte Zeitkomplexität jeder Operation ist konstant. Jedes Element der Liste wird höchstens einmal hinzugefügt, umgekehrt und entfernt. Um eine ineffiziente Operation beim Umkehren der hinteren Liste zu vermeiden, wird bei Echtzeit-Warteschlangen die Einschränkung eingeführt, dass die hintere Liste maximal so lang wie die vordere Liste sein darf. Damit die vordere Liste länger als die hintere bleibt, wird die hintere Liste umgekehrt und an die vordere Liste angehängt. Da diese Operation ineffizient ist, wird sie nicht sofort ausgeführt, sondern auf die nachfolgenden Operationen verteilt. So wird jedes Element berechnet, bevor es benötigt wird, und die neue vordere Liste ist vollständig berechnet, bevor eine neue ineffiziente Operation aufgerufen werden muss.

Siehe auch

Referenzen