Wie gehen rein funktionale Programmiersprachen mit sich schnell ändernden Daten um?

Welche Datenstrukturen können Sie verwenden, um O (1) zu entfernen und zu ersetzen? Oder wie können Sie Situationen vermeiden, in denen Sie diese Strukturen benötigen?

Es gibt eine Vielzahl von Datenstrukturen, die Faulheit und andere Tricks ausnutzen, um eine amortisierte konstante Zeit oder sogar (für einige begrenzte Fälle, wie Warteschlangen ) konstante Zeitaktualisierungen für viele Arten von Problemen zu erzielen . Chris Okasakis Doktorarbeit "Purely Functional Data Structures" und das gleichnamige Buch sind ein Paradebeispiel (vielleicht das erste große), aber das Gebiet hat sich seitdem weiterentwickelt . Diese Datenstrukturen haben normalerweise nicht nur eine rein funktionale Oberfläche, sondern können auch in reinen Haskell- und ähnlichen Sprachen implementiert werden und sind vollständig persistent.

Selbst ohne eines dieser fortschrittlichen Tools liefern einfache, ausgeglichene binäre Suchbäume Aktualisierungen in logarithmischer Zeit, so dass ein wandelbarer Speicher mit im schlimmsten Fall einer logarithmischen Verlangsamung simuliert werden kann.

Es gibt andere Optionen, die als Betrug betrachtet werden können, die jedoch hinsichtlich des Implementierungsaufwands und der tatsächlichen Leistung sehr effektiv sind. Beispielsweise ermöglichen lineare Typen oder Eindeutigkeitstypen eine direkte Aktualisierung als Implementierungsstrategie für eine konzeptionell reine Sprache, indem verhindert wird, dass das Programm den vorherigen Wert beibehält (den Speicher, der mutiert werden würde). Dies ist weniger allgemein als persistente Datenstrukturen: Sie können zum Beispiel nicht einfach ein Rückgängig-Protokoll erstellen, indem Sie alle vorherigen Versionen des Status speichern. Es ist immer noch ein leistungsfähiges Tool, obwohl AFAIK noch nicht in den wichtigsten funktionalen Sprachen verfügbar ist.

Eine weitere Möglichkeit, einen veränderlichen Zustand sicher in eine funktionale Umgebung STeinzufügen , ist die Monade in Haskell. Es kann ohne Mutation durchgeführt werden, und abgesehen von unsafe*Funktionen, es verhält sich , als wäre es nur ein schicker Wrapper um implizit eine persistente Datenstruktur vorbei (vgl State). Aufgrund einiger Tricks von Typsystemen, die die Reihenfolge der Auswertung erzwingen und das Entkommen verhindern, kann es jedoch mit In-Place-Mutation mit allen Leistungsvorteilen sicher implementiert werden.

Eine billige veränderbare Struktur ist der Argumentstapel.

Sehen Sie sich die typische faktorielle Berechnung nach SICP an:

(defn fac (n accum) 
    (if (= n 1) 
        accum 
        (fac (- n 1) (* accum n)))

(defn factorial (n) (fac n 1))

Wie Sie sehen können, wird das zweite Argument facals veränderlicher Akkumulator für das sich schnell ändernde Produkt verwendet n * (n-1) * (n-2) * .... Es ist jedoch keine veränderbare Variable in Sicht und es gibt keine Möglichkeit, den Akku versehentlich zu ändern, z. B. von einem anderen Thread.

Dies ist natürlich ein begrenztes Beispiel.

Sie können unveränderliche verknüpfte Listen durch billiges Ersetzen des Kopfknotens (und durch Erweiterung jedes Teils, das mit dem Kopf beginnt) erhalten: Sie bringen den neuen Kopf einfach auf denselben nächsten Knoten wie den alten Kopf. Dies funktioniert gut mit vielen Listenverarbeitungsalgorithmen (alles foldbasierend auf).

Assoziative Arrays, die z . B. auf HAMTs basieren, bieten eine recht gute Leistung . Logischerweise erhalten Sie ein neues assoziatives Array mit einigen geänderten Schlüssel-Wert-Paaren. Die Implementierung kann die meisten gemeinsamen Daten zwischen den alten und den neu erstellten Objekten gemeinsam nutzen. Dies ist jedoch nicht O (1); normalerweise erhält man etwas logarithmisches, zumindest im schlimmsten fall. Unveränderliche Bäume hingegen erleiden im Vergleich zu veränderlichen Bäumen normalerweise keine Leistungseinbußen. Dies erfordert natürlich einen gewissen Speicheraufwand, der normalerweise nicht unerschwinglich ist.

Ein anderer Ansatz basiert auf der Idee, dass ein Baum, der in einen Wald fällt und von niemandem gehört wird, keinen Ton produzieren muss. Wenn Sie also nachweisen können, dass ein Teil des mutierten Zustands niemals einen lokalen Bereich verlässt, können Sie die darin enthaltenen Daten sicher mutieren.

Clojure weist Transienten auf , die veränderbare "Schatten" unveränderlicher Datenstrukturen sind, die nicht außerhalb des lokalen Bereichs durchgesickert sind. Clean nutzt Uniques, um etwas Ähnliches zu erreichen (wenn ich mich richtig erinnere). Rust hilft bei ähnlichen Aufgaben mit statisch überprüften eindeutigen Zeigern.

Was Sie fragen, ist ein bisschen zu breit. O (1) Entfernen und Ersetzen aus welcher Position? Der Kopf einer Sequenz? Der Schweif? Eine beliebige Position? Die zu verwendende Datenstruktur hängt von diesen Details ab. Das sei gesagt, 2-3 Finger Bäume scheinen , wie einer der vielseitigsten persistente Datenstrukturen da draußen:

Wir präsentieren 2-3 Fingerbäume, eine funktionale Darstellung von persistenten Sequenzen, die den Zugang zu den Enden in amortisierter konstanter Zeit unterstützen, und Verkettung und zeitliche Aufteilung logarithmisch in der Größe des kleineren Stücks.

(...)

Durch Definieren der Aufteilungsoperation in einer allgemeinen Form erhalten wir eine allgemeine Datenstruktur, die als Sequenz, Prioritätswarteschlange, Suchbaum, Prioritätssuchwarteschlange und mehr dienen kann.

Im Allgemeinen weisen persistente Datenstrukturen eine logarithmische Leistung auf, wenn beliebige Positionen geändert werden. Dies kann ein Problem sein oder auch nicht, da die Konstante in einem O (1) -Algorithmus hoch sein kann und die logarithmische Verlangsamung in einem langsameren Gesamtalgorithmus "absorbiert" werden kann.

Noch wichtiger ist, dass persistente Datenstrukturen das Denken in Bezug auf Ihr Programm erleichtern. Dies sollte immer Ihre Standardbetriebsart sein. Sie sollten beständige Datenstrukturen nach Möglichkeit bevorzugen und erst dann eine veränderbare Datenstruktur verwenden, wenn Sie ein Profil erstellt und festgestellt haben, dass die beständige Datenstruktur ein Leistungsengpass ist. Alles andere ist vorzeitige Optimierung.