Was ist die Datenstruktur Zipper und sollte ich es verwenden?

Question

Die Frage ist einfach: Ich kann nicht die Zipper Strukturdaten verstehen.

Meine Frage bezieht sich auf seine Verwendung mit einem Baum.

Ich möchte verstehen, wie kann ich den Baumknoten mit Reißverschluss ändern. Und wie nicht den ganzen Baum zu kopieren (oder den größten Teil davon).

Bitte klären, ob ich mit Reißverschluss falsch bin. Vielleicht kann es nicht mit dem Baum-Update helfen?
Oder vielleicht ist es möglich, den Baum zu aktualisieren, und ich kann einfach nicht die Art und Weise sehen?

Answer 1

Lassen Sie uns mit dem Reißverschluss-Analog für Listen starten. Wenn Sie das n-te Element einer Liste ändern mögen, dauert es O (n), weil Sie die n-1 ersten Elemente zu kopieren. Stattdessen sehen Sie die Liste als eine Struktur halten ((erster n-1 Element umgekehrt) n-te Element (übrige Elemente)). Zum Beispiel würde die Liste (1 2 3 4 5 6) modifizierbar bei 3 als ((2 1) 3 (4 5 6)) dargestellt werden. Jetzt können Sie leicht sonst die 3 bis etwas ändern. Sie können auch den Fokus links und rechts ((1) 2 (3 4 5 6)) ((3 2 1) 4 (5 6)) leicht bewegen lassen.

Ein Reißverschluss ist die gleiche Idee auf Bäumen angelegt. Sie stellen einen bestimmten Fokus im Baum sowie einen Rahmen (bis zu Eltern, bis hin zu Kindern), die Ihnen den ganzen Baum in einer Form gibt, wo es in dem Fokus leicht modifizierbar ist und es ist leicht, den Fokus nach oben und unten zu bewegen.

Answer 2

Hier ist ein sehr schöner Artikel erklärt den Reißverschluss für ein Tiling in Haskell verwenden. Der Wikipedia-Artikel ist keine gute Referenz.

Kurz gesagt, ist der Reißverschluß ein Zeiger oder Griff an einem bestimmten Knoten in einer Baumstruktur oder einer Liste. Der Reißverschluss gibt eine natürliche Art und Weise eine Baumstruktur des Nehmen und Behandlung es, als ob der Baum „abgeholt“ durch den fokussierten Knoten - in der Tat, können Sie einen zweiten Baum erhalten, ohne dass zusätzliche Kopien des ursprünglichen Baumes oder Auswirkungen auf andere Nutzer der Baum.

Das Beispiel zeigt, wie man die Fenster ursprünglich von Position auf dem Bildschirm sortiert, und dann zu modellieren konzentrieren Sie verwenden ein Reißverschluss im Fokus Fenster zeigte. Sie erhalten eine schöne Reihe von O (1) Operationen wie Einfügen und löschen, ohne den Fokus Fenster Sonderfall mit oder zusätzlichen Code schreiben.

Answer 3

Erfahren Sie ein Haskell hat auch ein großes Kapitel über Reißverschlüsse .

Answer 4

Dieser Artikel ist Haskell, aber es erklärt auch, Reißverschlüsse ziemlich gut und es sollte aus dem Haskell-Spezifika zu abstrahieren einfach sein.