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

11

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.

Alexey
quelle
4
Empfohlen: Okasaki
Robert Harvey
2
Danke für den Hinweis. Ich habe seine These gefunden .
Alexey
Dieses Papier sieht vielversprechend aus: Lazy Deep-First-Suche und lineare Graph-Algorithmen in Haskell (1994) von David King und John Launchbury.
Alexey
Es sieht so aus, als würde ein ähnliches Problem mit Arrays durch ein Diffarray- Paket behoben , das den DiffArrayTyp implementiert . Wenn ich mir die Quelle des Diffarray- Pakets anschaue , sehe ich 91 Vorkommen von unsafePerformIO. Die Antwort auf meine Frage lautet anscheinend "Ja, nein, rein funktionale Sprachen mit unveränderlichen Daten sind nicht für die Implementierung von Algorithmen geeignet, die normalerweise auf direkten Aktualisierungen beruhen".
Alexey
Meine aktuelle Lösung (in Haskell) ist ein Wörterbuch zu verwenden ( Map, IntMapoder HashMap) als Speicher- und Knoten - IDs der verknüpften Knoten enthalten zu machen. "Alle Probleme in der Informatik können durch eine andere Indirektionsebene gelöst werden."
Alexey

Antworten:

6

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.

9000
quelle
1
Je nachdem, was benötigt wird, kann auch ein Reißverschluss nützlich sein
jk.
Um mein Problem enger zu spezifizieren, nehme ich an, ich möchte ein Graph-Rewriting-System programmieren, zum Beispiel einen Lambda-Kalkül-Evaluator, der auf Graph-Rewriting basiert.
Alexey
1
@Alexey: Kennen Sie die Arbeit der Clean People beim Umschreiben von Grafiken? wiki.clean.cs.ru.nl/…
Giorgio
1
@ Alexander: Nicht dass ich es wüsste: Clean ist ein Cousin von Haskell, der selbst entwickelt wurde. Es hat auch einen anderen Mechanismus für den Umgang mit Nebenwirkungen (AFAIK nennt man einzigartige Typen). Auf der anderen Seite haben die Entwickler viel mit dem Umschreiben von Graphen gearbeitet. Sie könnten also zu den besten Leuten gehören, die sich sowohl mit dem Umschreiben von Graphen als auch mit der funktionalen Programmierung auskennen.
Giorgio
1
Ich bin damit einverstanden, dass ein Reißverschluss das Problem mit einer doppelt verknüpften Liste oder einem Baum zu lösen scheint, wenn ich darin navigieren und an der Stelle ändern möchte, an der ich mich gerade befinde, aber es ist nicht klar, was zu tun ist, wenn ich mich auf mehrere Stellen konzentrieren möchte gleichzeitig und tauschen Sie beispielsweise zwei Elemente an zwei weit voneinander entfernten Stellen aus. Es ist noch weniger klar, ob es mit "kreisförmigen" Strukturen verwendet werden kann.
Alexey
2

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 .

Jules
quelle
Danke, ich werde versuchen, etwas über STM zu lernen. Es sieht aus wie es mehr Methoden in Haskell ist Veränderlichkeit zu haben und Zustand (ich habe stolpert MVar, State, ST), so dass ich , um ihre Unterschiede zu Figur benötigen und beabsichtigten Anwendungen.
Alexey
@Alexey: Guter Punkt in Bezug auf STIMO sollte es in der Antwort erwähnt werden, da es ermöglicht, eine zustandsbehaftete Berechnung auszuführen, dann den Zustand wegzuwerfen und das Ergebnis als reinen Wert zu extrahieren.
Giorgio
@Giorgio, ist es möglich, Haskell's STmit STM zu verwenden, um sowohl Parallelität als auch verfügbaren Status zu haben?
Alexey
Nur noch ein Terminologie Vorschlag: die zusammengesetzte Hauptaktion IO nicht „ zurückgeführt durch die Hauptfunktion“ ist jedoch nicht auf zugeordneten mainVariablen. :) ( mainhält nicht einmal eine Funktion.)
Alexey
Ich verstehe Ihren Standpunkt, aber "variabel" hat in den meisten Köpfen eine Konnotation als einfachen Wert und nicht als einen Prozess, der einen Wert erzeugt, und main wird eindeutig besser als letzterer als als ersterer angesehen. Die von Ihnen vorgeschlagene Änderung ist zwar technisch eindeutig korrekt, kann jedoch diejenigen verwirren, die mit dem Thema nicht vertraut sind.
Jules