Rein funktionale Datenstruktur – Wikipedia

In der Informatik a rein funktionale Datenstruktur ist eine Datenstruktur, die in einer rein funktionalen Sprache implementiert werden kann. Der Hauptunterschied zwischen einer beliebigen und einer rein funktionalen Datenstruktur besteht darin, dass letztere (stark) unveränderlich ist. Diese Einschränkung stellt sicher, dass die Datenstruktur die Vorteile unveränderlicher Objekte besitzt: (vollständige) Persistenz, schnelles Kopieren von Objekten und Thread-Sicherheit. Effiziente rein funktionale Datenstrukturen erfordern möglicherweise die Verwendung einer verzögerten Auswertung und Speicherung.

Definition[edit]

Persistente Datenstrukturen haben die Eigenschaft, frühere Versionen von sich selbst unverändert zu lassen. Andererseits lassen Strukturen wie Arrays zu destruktives Update,^[1] Das heißt, ein Update, das nicht abgebrochen werden kann. Sobald ein Programm einen Wert in einen Index des Arrays schreibt, kann sein vorhergehender Wert nicht mehr abgerufen werden.^{[citation needed]}

Formal a Rein funktionale Datenstruktur ist eine Datenstruktur, die in einer rein funktionalen Sprache wie Haskell implementiert werden kann. In der Praxis bedeutet dies, dass die Datenstrukturen nur mit persistenten Datenstrukturen wie Tupeln, Summentypen, Produkttypen und Basistypen wie Ganzzahlen, Zeichen und Zeichenfolgen erstellt werden müssen. Eine solche Datenstruktur ist notwendigerweise persistent. Alle persistenten Datenstrukturen sind jedoch nicht rein funktional.^[1]::16 Beispielsweise ist ein beständiges Array eine Datenstruktur, die beständig ist und die unter Verwendung eines Arrays implementiert wird und daher nicht rein funktional ist.^{[citation needed]}

Im Buch Rein funktionale Datenstrukturen, Okasaki vergleicht zerstörerische Aktualisierungen mit den Messern des Meisterkochs.^[1]::2 Destruktive Aktualisierungen können nicht rückgängig gemacht werden und sollten daher nicht verwendet werden, es sei denn, es ist sicher, dass der vorherige Wert nicht mehr benötigt wird. Destruktive Aktualisierungen können jedoch auch eine Effizienz ermöglichen, die mit anderen Techniken nicht erreicht werden kann. Beispielsweise kann eine Datenstruktur, die ein Array und destruktive Aktualisierungen verwendet, durch eine ähnliche Datenstruktur ersetzt werden, wobei das Array durch eine Karte, eine Direktzugriffsliste oder einen ausgeglichenen Baum ersetzt wird, der eine rein funktionale Implementierung zulässt. Die Zugriffskosten können sich jedoch von konstanter Zeit zu logarithmischer Zeit erhöhen.^{[citation needed]}

Sicherstellen, dass eine Datenstruktur rein funktionsfähig ist[edit]

Eine Datenstruktur ist niemals von Natur aus funktionsfähig. Beispielsweise kann ein Stapel als einfach verknüpfte Liste implementiert werden. Diese Implementierung ist rein funktional, solange die einzigen Operationen auf dem Stapel einen neuen Stapel zurückgeben, ohne den alten Stapel zu ändern. Wenn die Sprache jedoch nicht rein funktionsfähig ist, kann das Laufzeitsystem möglicherweise keine Unveränderlichkeit garantieren. Dies wird von Okasaki illustriert,^[1]::9-11 wo er die Verkettung von zwei einfach verknüpften Listen zeigt, kann immer noch mit einer imperativen Einstellung erfolgen.^{[citation needed]}

Um sicherzustellen, dass eine Datenstruktur in einer unreinen Funktionssprache rein funktional verwendet wird, können Module oder Klassen verwendet werden, um die Manipulation nur über autorisierte Funktionen sicherzustellen.^{[citation needed]}

Rein funktionale Datenstrukturen verwenden[edit]

Eine der zentralen Herausforderungen bei der Anpassung des vorhandenen Codes an rein funktionale Datenstrukturen besteht darin, dass veränderbare Datenstrukturen “versteckte Ausgaben” für Funktionen bereitstellen, die sie verwenden. Um diese Funktionen umzuschreiben, um rein funktionale Datenstrukturen zu verwenden, müssen diese Datenstrukturen als explizite Ausgaben hinzugefügt werden.

Stellen Sie sich beispielsweise eine Funktion vor, die eine veränderbare Liste akzeptiert, ein Element in die Liste einfügt und die Länge der neuen Liste zurückgibt. In einer rein funktionalen Einstellung wird durch Einfügen eines neuen Elements in die Liste eine neue Liste erstellt, die ursprüngliche jedoch nicht aktualisiert. Um nützlich zu sein, muss eine rein funktionale Version dieser Funktion wahrscheinlich sowohl die Länge der Liste als auch die neue Liste selbst zurückgeben. Im allgemeinsten Fall muss ein auf diese Weise konvertiertes Programm den “Status” oder “Speicher” des Programms als zusätzliches Ergebnis aus jedem Funktionsaufruf zurückgeben. Ein solches Programm soll im Store-Passing-Stil geschrieben sein.

Beispiele[edit]

Hier ist eine Liste abstrakter Datenstrukturen mit rein funktionalen Implementierungen:

• Stapel (first in, last out) als einfach verknüpfte Liste implementiert,
• Warteschlange, implementiert als Echtzeitwarteschlange,
• Double-Ended-Warteschlange, implementiert als Double-Ended-Warteschlange in Echtzeit,
• (Multi) Satz geordneter Elemente und Karte, indiziert durch geordnete Schlüssel, implementiert als rot-schwarzer Baum oder allgemeiner durch einen Suchbaum.
• Prioritätswarteschlange, implementiert als Brodal-Warteschlange
• Random Access List, implementiert als skew-binäre Random Access List
• Hash consing
• Reißverschluss (Datenstruktur)

Design und Implementierung[edit]

In seinem Buch Rein funktionale DatenstrukturenDer Informatiker Chris Okasaki beschreibt Techniken zum Entwerfen und Implementieren rein funktionaler Datenstrukturen, von denen eine kleine Teilmenge im Folgenden zusammengefasst ist.

Faulheit und Auswendiglernen[edit]

Lazy Evaluation ist besonders interessant in einer rein funktionalen Sprache^[1]::31 weil die Reihenfolge der Auswertung niemals das Ergebnis einer Funktion ändert. Eine verzögerte Auswertung wird daher natürlich zu einem wichtigen Bestandteil beim Aufbau rein funktionaler Datenstrukturen. Berechnungen können nur durchgeführt werden, wenn das Ergebnis tatsächlich erforderlich ist. Daher kann der Code einer rein funktionalen Datenstruktur ohne Effizienzverlust ähnliche Daten berücksichtigen, die effektiv verwendet werden, und Daten, die ignoriert werden. Die einzige Berechnung, die erforderlich ist, bezieht sich auf die erste Art von Daten, die tatsächlich ausgeführt werden.^{[citation needed]}

Eines der wichtigsten Werkzeuge beim Aufbau effizienter, rein funktionaler Datenstrukturen ist das Auswendiglernen.^[1]::31 Wenn eine Berechnung durchgeführt wurde, wird sie gespeichert und muss nicht ein zweites Mal durchgeführt werden. Dies ist besonders wichtig bei verzögerten Implementierungen. Zusätzliche Bewertungen erfordern möglicherweise das gleiche Ergebnis, es ist jedoch unmöglich zu wissen, für welche Bewertung dies zuerst erforderlich ist.^{[citation needed]}

Amortisierte Analyse und Planung[edit]

Einige Datenstrukturen, auch solche, die nicht rein funktional sind, wie z. B. dynamische Arrays, lassen einen Betrieb zu, der die meiste Zeit effizient (dh konstante Zeit für dynamische Arrays) und selten ineffizient (dh lineare Zeit für dynamische Arrays) ist. Amortisation kann dann verwendet werden, um zu beweisen, dass die durchschnittliche Laufzeit der Operationen effizient ist.^[1]::39 Das heißt, die wenigen ineffizienten Operationen sind selten genug und ändern nicht die asymptotische Entwicklung der Zeitkomplexität, wenn eine Folge von Operationen betrachtet wird.^{[citation needed]}

Im Allgemeinen ist es für persistente Datenstrukturen nicht akzeptabel, ineffiziente Operationen durchzuführen, da genau diese Operation viele Male aufgerufen werden kann. Dies ist weder für Echtzeit- noch für imperative Systeme akzeptabel, bei denen der Benutzer möglicherweise benötigt, dass die von der Operation benötigte Zeit vorhersehbar ist. Darüber hinaus erschwert diese Unvorhersehbarkeit die Verwendung von Parallelität.^{[1]::83[citation needed]}

Um diese Probleme zu vermeiden, können Sie bei einigen Datenstrukturen den ineffizienten Betrieb verschieben – dies wird als Zeitplanung bezeichnet.^[1]::84 Die einzige Voraussetzung ist, dass die Berechnung der ineffizienten Operation endet, bevor das Ergebnis tatsächlich benötigt wird. Ein konstanter Teil der ineffizienten Operation wird gleichzeitig mit dem folgenden Aufruf einer effizienten Operation ausgeführt, so dass die ineffiziente Operation bereits vollständig ausgeführt wird, wenn sie benötigt wird, und jede einzelne Operation effizient bleibt.^{[clarification needed]}

Beispiel: Warteschlange[edit]

Amortisierte Warteschlangen^{[1]::65[1]::73} bestehen aus zwei einzeln verknüpften Listen: der vorderen und der umgekehrten Rückseite. Elemente werden der hinteren Liste hinzugefügt und aus der vorderen Liste entfernt. Wenn die vordere Warteschlange leer ist, wird die hintere Warteschlange umgekehrt und wird zur vorderen, während die hintere Warteschlange leer wird. Die amortisierte Zeitkomplexität jeder Operation ist konstant. Jede Zelle der Liste wird höchstens einmal hinzugefügt, umgekehrt und entfernt. Um einen ineffizienten Vorgang zu vermeiden, bei dem die hintere Liste umgekehrt wird, fügen Echtzeitwarteschlangen die Einschränkung hinzu, dass die hintere Liste nur so lang ist wie die vordere Liste. Um sicherzustellen, dass die hintere Liste länger als die vordere Liste wird, wird die vordere Liste an die hintere Liste angehängt und umgekehrt. Da dieser Vorgang ineffizient ist, wird er nicht sofort ausgeführt. Stattdessen wird es für jede der Operationen ausgeführt. Somit wird jede Zelle berechnet, bevor sie benötigt wird, und die neue Frontliste wird vollständig berechnet, bevor eine neue ineffiziente Operation aufgerufen werden muss.^{[citation needed]}

Siehe auch[edit]

Verweise[edit]

Externe Links[edit]