Rein funktionale Datenstruktur - Purely functional data structure

In der Informatik ist eine rein funktionale Datenstruktur eine Datenstruktur , die in einer rein funktionalen Sprache implementiert werden kann . Der Hauptunterschied zwischen einer beliebigen Datenstruktur und einer rein funktionalen besteht darin, dass letztere (stark) unveränderlich ist . Diese Einschränkung stellt sicher, dass die Datenstruktur die Vorteile unveränderlicher Objekte besitzt: (volle) Persistenz , schnelles Kopieren von Objekten und Thread-Sicherheit . Effiziente rein funktionale Datenstrukturen können den Einsatz von Lazy Evaluation und Memoization erfordern .

Definition

Persistente Datenstrukturen haben die Eigenschaft, frühere Versionen von sich selbst unverändert zu lassen. Andererseits lassen Strukturen wie Arrays eine destruktive Aktualisierung zu , dh eine Aktualisierung , die nicht rückgängig gemacht werden kann. Sobald ein Programm einen Wert in einen Index des Arrays schreibt, kann sein vorheriger Wert nicht mehr abgerufen werden.

Formal 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 nur unter Verwendung von persistenten Datenstrukturen wie Tupeln, Summentypen , Produkttypen und Basistypen wie Integer, Zeichen, Strings aufgebaut werden dürfen. Eine solche Datenstruktur ist notwendigerweise persistent. Allerdings sind nicht alle persistenten Datenstrukturen rein funktional. Ein persistentes Array ist beispielsweise eine persistente Datenstruktur, die unter Verwendung eines Arrays implementiert wird, also nicht rein funktional ist.

In dem Buch Rein funktionale Datenstrukturen vergleicht Okasaki destruktive Updates mit Meisterkochmessern. Destruktive Updates können nicht rückgängig gemacht werden und sollten daher nicht verwendet werden, es sei denn, der vorherige Wert wird nicht mehr benötigt. Jedoch können destruktive Aktualisierungen 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 Liste mit wahlfreiem Zugriff oder einen ausgeglichenen Baum ersetzt wird , was eine rein funktionale Implementierung zulässt. Die Zugriffskosten können jedoch von konstanter Zeit zu logarithmischer Zeit steigen .

Sicherstellen, dass eine Datenstruktur rein funktional ist

Eine Datenstruktur ist niemals von Natur aus funktional. Beispielsweise kann ein Stack als einfach verknüpfte Liste implementiert werden . Diese Implementierung ist rein funktional, solange die einzigen Operationen auf dem Stack einen neuen Stack zurückgeben, ohne den alten Stack zu ändern. Wenn die Sprache jedoch nicht rein funktional ist, kann das Laufzeitsystem möglicherweise keine Unveränderlichkeit garantieren. Dies wird von Okasaki veranschaulicht, wo er zeigt, dass die Verkettung zweier einzeln verknüpfter Listen immer noch mit einer Imperativeinstellung erfolgen kann.

Um sicherzustellen, dass eine Datenstruktur rein funktional in einer unreinen funktionalen Sprache verwendet wird, können Module oder Klassen verwendet werden, um eine Manipulation nur über autorisierte Funktionen sicherzustellen.

Verwendung rein funktionaler Datenstrukturen

Eine der zentralen Herausforderungen bei der Anpassung von bestehendem Code an rein funktionale Datenstrukturen besteht darin, dass veränderliche Datenstrukturen „versteckte Ausgaben“ für Funktionen bereitstellen, die sie verwenden. Das Umschreiben dieser Funktionen, um rein funktionale Datenstrukturen zu verwenden, erfordert das Hinzufügen dieser Datenstrukturen als explizite Ausgaben.

Betrachten Sie beispielsweise eine Funktion, die eine veränderliche Liste akzeptiert, ein Element in die Liste einfügt und die Länge der neuen Liste zurückgibt. In einer rein funktionalen Einstellung erzeugt das Einfügen eines neuen Elements in die Liste eine neue Liste, aktualisiert jedoch nicht die ursprüngliche. Um nützlich zu sein, muss eine rein funktionale Version dieser Funktion daher wahrscheinlich sowohl die Länge der Liste als auch die neue Liste selbst zurückgeben. Im allgemeinsten Fall muss ein so konvertiertes Programm bei jedem Funktionsaufruf als zusätzliches Ergebnis den "Zustand" oder "Speicher" des Programms zurückliefern. Man sagt, dass ein solches Programm im Store-Passing-Stil geschrieben ist .

Beispiele

Hier ist eine Liste abstrakter Datenstrukturen mit rein funktionalen Implementierungen:

Konzeption und Umsetzung

In seinem Buch Purely Functional Data Structures beschreibt der Informatiker Chris Okasaki Techniken zum Entwerfen und Implementieren rein funktionaler Datenstrukturen, von denen im Folgenden eine kleine Teilmenge zusammengefasst wird.

Faulheit und Auswendiglernen

Lazy Evaluation ist in einer rein funktionalen Sprache besonders interessant, da die Reihenfolge der Evaluation das Ergebnis einer Funktion nie ändert. Daher wird die Lazy-Evaluation natürlich ein wichtiger Bestandteil beim Aufbau rein funktionaler Datenstrukturen. Es erlaubt eine Berechnung nur dann durchzuführen, wenn das Ergebnis tatsächlich benötigt wird. Daher kann der Code einer rein funktionalen Datenstruktur ohne Effizienzverlust Daten, die effektiv genutzt werden, und Daten, die ignoriert werden, gleichermaßen berücksichtigen. Die einzige erforderliche Berechnung gilt für die erste Art von Daten; das wird tatsächlich ausgeführt.

Eines der wichtigsten Werkzeuge beim Aufbau effizienter, rein funktionaler Datenstrukturen ist die Memoisierung. Wenn eine Berechnung abgeschlossen ist, wird sie gespeichert und muss nicht ein zweites Mal durchgeführt werden. Dies ist besonders bei trägen Implementierungen wichtig; zusätzliche Auswertungen können das gleiche Ergebnis erfordern, aber es ist unmöglich zu wissen, welche Auswertung es zuerst erfordert.

Amortisierte Analyse und Planung

Einige Datenstrukturen, sogar solche, die nicht rein funktional sind, wie beispielsweise dynamische Arrays , lassen Operationen zu, die die meiste Zeit effizient sind (zB konstante Zeit für dynamische Arrays) und selten ineffizient (zB lineare Zeit für dynamische Arrays). Mit der Amortisation kann dann nachgewiesen werden, dass die durchschnittliche Laufzeit der Operationen effizient ist. Das heißt, die wenigen ineffizienten Operationen sind selten genug und ändern nichts an der asymptotischen Entwicklung der Zeitkomplexität, wenn eine Folge von Operationen betrachtet wird.

Im Allgemeinen sind ineffiziente Operationen für persistente Datenstrukturen nicht akzeptabel, da genau diese Operation viele Male aufgerufen werden kann. Es ist weder für Echtzeit- noch für zwingende Systeme akzeptabel, bei denen der Benutzer möglicherweise eine vorhersehbare Zeit für die Operation wünscht. Darüber hinaus erschwert diese Unvorhersehbarkeit die Verwendung von Parallelität .

Um diese Probleme zu vermeiden, ermöglichen einige Datenstrukturen, dass der ineffiziente Vorgang verschoben wird – dies wird als Scheduling bezeichnet . Die einzige Anforderung besteht darin, dass die Berechnung der ineffizienten Operation beendet wird, bevor ihr 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 bei Bedarf bereits vollständig durchgeführt wird und jede einzelne Operation effizient bleibt.

Beispiel: Warteschlange

Amortisierte Warteschlangen bestehen aus zwei einzeln verknüpften Listen: der vorderen und der umgekehrten hinteren. Elemente werden der hinteren Liste hinzugefügt und aus der vorderen Liste entfernt. Außerdem wird, wenn die vordere Schlange leer ist, die hintere Schlange umgekehrt und wird zur vorderen, während die hintere Schlange leer wird. Die amortisierte Zeitkomplexität jeder Operation ist konstant. Jede Zelle der Liste wird höchstens einmal hinzugefügt, umgekehrt und entfernt. Um eine ineffiziente Operation zu vermeiden, bei der die hintere Liste umgekehrt wird, fügen Echtzeitwarteschlangen die Einschränkung hinzu, dass die hintere Liste nur so lang wie die vordere Liste ist. Damit die hintere Liste länger wird als die vordere Liste, 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 auf die nachfolgenden Operationen verteilt. 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.

Siehe auch

Verweise

Externe Links