Problemumgehung für die Implementierung von Vorgängen für doppelt verknüpfte oder zirkuläre Datenstrukturen in Sprachen mit unveränderlichen Daten

Ich würde gerne lernen, wie man in Haskell Diagramme erstellt und einige lokale Operationen daran ausführt, aber die Frage ist nicht spezifisch für Haskell, und anstelle von Diagrammen können wir doppelt verknüpfte Listen betrachten.

Frage: Was wäre eine idiomatische oder empfohlene Methode, um eine doppelt verknüpfte Liste (oder eine andere doppelt verknüpfte oder zirkuläre Datenstruktur) und Operationen darauf in einer Sprache zu implementieren, die hauptsächlich unveränderliche Datenstrukturen unterstützt und befürwortet (Haskell, Clojure usw.)? ? Insbesondere, wie man In-Place-Updates verwendet, die von der Sprache formal verboten sind?

Ich kann mir leicht vorstellen, dass es aufgrund der Faulheit der Sprache möglicherweise nicht erforderlich ist, die gesamte Liste sofort zu kopieren, wenn eine lokale Operation für eine doppelt verknüpfte Liste ausgeführt wird (z. B. wenn ein Element eingefügt wird). Da die Liste jedoch doppelt verknüpft ist, kann keiner der alten Knoten in der neuen Version der Liste verwendet werden, wenn sie an einer Stelle geändert wird, und sie müssten früher oder später irgendwie markiert, kopiert und mit Müll gesammelt werden . Offensichtlich sind dies redundante Operationen, wenn nur die aktualisierte Kopie der Liste verwendet werden soll, aber sie würden einen "Overhead" hinzufügen, der proportional zur Größe der Liste ist.

Bedeutet dies, dass unveränderliche Daten für solche Aufgaben einfach unangemessen sind und funktionale deklarative Sprachen ohne "native" Unterstützung für veränderbare Daten nicht so gut sind wie zwingende? Oder gibt es eine schwierige Problemumgehung?

PS Ich habe einige Artikel und Präsentationen zu diesem Thema im Internet gefunden, hatte aber Schwierigkeiten, ihnen zu folgen, während ich denke, dass die Antwort auf diese Frage nicht mehr als einen Absatz und vielleicht ein Diagramm umfassen sollte ... Ich meine, wenn es welche gibt Keine "funktionale" Lösung für dieses Problem, die Antwort lautet wahrscheinlich "benutze C". Wenn es eine gibt, wie kompliziert kann sie dann sein?

Verwandte Fragen

• "Datenstrukturen in der funktionalen Programmierung" . Meine spezielle Frage zur Verwendung von In-Place-Updates anstelle ineffizienter Alternativen wird dort nicht erörtert.

• "Interne Mutation persistenter Datenstrukturen" . Dort scheint der Schwerpunkt auf der Implementierung auf niedriger Ebene in einer nicht spezifizierten Sprache zu liegen, während meine Frage die richtige Wahl einer Sprache (funktional oder anderweitig) und mögliche idiomatische Lösungen in funktionalen Sprachen betrifft.

Relevante Zitate

Rein funktionale Programmiersprachen ermöglichen es, viele Algorithmen sehr präzise auszudrücken, aber es gibt einige Algorithmen, bei denen der aktuelle aktualisierbare Zustand eine entscheidende Rolle zu spielen scheint. Für diese Algorithmen scheinen rein funktionale Sprachen, denen der aktualisierbare Zustand fehlt, von Natur aus ineffizient zu sein ( [Ponder, McGeer und Ng, 1988] ).

- John Launchbury und Simon Peyton Jones, Lazy Functional State Threads (1994), auch John Launchbury und Simon Peyton Jones, State in Haskell (1995). Diese Arbeiten stellen den STmonadischen Konstruktor in Haskell vor.

Es könnte andere effiziente unveränderliche Datenstrukturen geben, die zu Ihrer speziellen Aufgabe passen, aber nicht so allgemein sind wie eine doppelt verknüpfte Liste (die aufgrund ihrer Veränderlichkeit leider zu gleichzeitigen Änderungsfehlern neigt ). Wenn Sie Ihr Problem enger spezifizieren, kann eine solche Struktur wahrscheinlich gefunden werden.

Die allgemeine Antwort für das (relativ) wirtschaftliche Durchqueren unveränderlicher Strukturen sind Linsen. Die Idee ist, dass Sie gerade genug Informationen behalten können, um eine modifizierte unveränderliche Struktur aus ihren nicht modifizierten Teilen und dem aktuell modifizierten Teil zu rekonstruieren und darüber zu einem benachbarten Knoten zu navigieren.

Eine weitere nützliche Struktur ist ein Reißverschluss . (Der lustige Teil ist, dass die Typensignatur für einen Objektivreißverschluss eine schulmathematische Ableitung einer Typensignatur der Struktur ist.)

Hier sind ein paar Links.

• Eine einfache Erklärung der Reißverschlüsse

• Ein Kapitel über Reißverschlüsse aus "Learn you a Haskell"

• Einführung in Objektive in Scala (Dias)

• Grundlegende Linse
• Objektive in der funktionalen Programmierung

Haskell verhindert nicht die Verwendung veränderlicher Datenstrukturen. Sie werden stark entmutigt und sind schwieriger zu verwenden, da die Teile des Codes, die sie verwenden, möglicherweise eine E / A-Aktion zurückgeben müssen (die schließlich an die E / A-Aktion gebunden sein muss, die von der Hauptfunktion zurückgegeben wird), dies jedoch nicht Machen Sie es unmöglich, solche Strukturen zu verwenden, wenn Sie sie wirklich brauchen.

Ich würde vorschlagen, die Verwendung von Software-Transaktionsspeicher als einen Weg nach vorne zu untersuchen. Es bietet nicht nur eine effiziente Möglichkeit zur Implementierung veränderlicher Strukturen, sondern auch sehr nützliche Garantien für die Thread-Sicherheit. Siehe die Modulbeschreibung unter https://hackage.haskell.org/package/stm und die Wiki-Übersicht unter https://wiki.haskell.org/Software_transactional_memory .