Lokal einen rein funktionalen Baum bearbeiten

Question

Lokal einen rein funktionalen Baum bearbeiten

9

Definieren wir einen Baum T:

%Vor%

Nehmen wir an, ein neuer Knoten wird zu E hinzugefügt, was T 'ergibt:

%Vor%

In einer veränderlichen Sprache ist das eine leichte Aufgabe - update einfach E's Kinder und wir sind fertig. In einer unveränderlichen Welt ist es jedoch notwendig, zuerst den Pfad zu E zu kennen, dann E 'von E + neues Kind abzuleiten, dann B' und dann schließlich A '(= T') abzuleiten.

Das ist umständlich; Idealerweise würde es eine Funktion geben, die die Werte von E und G (und möglicherweise T) annehmen und T 'erzeugen würde, ohne den Pfad zu E zu liefern.

Ich sehe zwei Möglichkeiten, dieses Problem anzugehen:

Elternreferenzen - Auf diese Weise kann jeder Knoten seinen Pfad zum Stamm ableiten. Zwei Probleme: das Erstellen von zwei sich gegenseitig verweisenden Knoten (d. H. Elternteil & lt; - & gt; Kind) ist ein Problem in einer rein funktionalen Sprache (irgendwelche einfachen Lösungen?); und wann immer E - & gt; E 'ist abgeleitet, alle von E' Kindern müssen ebenfalls neu abgeleitet werden, da sie jetzt den alten Wert von E anstelle von E 'speichern.
Reißverschlüsse - jeder Knoten speichert einen Reißverschluss, der von seinem Reißverschluß stammt. Das sich gegenseitig verweisende Problem verschwindet, aber immer noch, wenn E - & gt; E 'ist abgeleitet, alle E' Kinder 'Reißverschlüsse müssen ebenfalls abgeleitet werden, da sie jetzt auf den alten Baum E zeigen.

Ist das, was ich begehre, auch mit einer vernünftigen Leistung möglich? Vielen Dank für etwaige Eingaben!

tree immutability purely-functional zipper

Philip Kamenarsky 26.01.2012, 23:11

quelle

1 Antwort

Tags und Links tree immutability purely-functional zipper

Django: Verwenden von Annotate, Count und Distinct in einem Queryset Zugriff auf stdin während des Systemd Bootvorgangs

score 1 · Answer 1

Eine andere Option, basierend auf einem Lazy Replace. Wenn es leistungskritisch ist und viele Änderungen daran vorgenommen werden, würde ich vorschlagen, es zu bewerten.

Ich habe es in F # implementiert, aber ich glaube nicht, dass ich etwas "inpure" außer meiner Druckfunktion verwendet habe.

Dies ist ein Stück Text, Das Grundprinzip ist, den Baum Faul zu halten, Ersetzen Sie die Knoten, indem Sie die Funktion ersetzen, die den Knoten zurückgibt.

Der Trick besteht darin, dass Sie einen Weg brauchen, um einen Knoten zu identifizieren, der nicht seine eigene Referenz / Name ist und nicht nach Wert. Die Identifikation muss auf die ReplacementNodes duplizierbar sein In diesem Fall habe ich System.Object's so verwendet, wie sie referentiell jeweils verschieden sind.

%Vor%

Testfall / Beispiel:

%Vor%

Wir haben am Ende des Tests gesehen, dass die Verwendung eines alten Knotens Name (/ reference) für das zu ersetzende Objekt nicht funktioniert. Es besteht die Möglichkeit, einen neuen Typ mit der Referenz-ID eines anderen Knotens zu erstellen:

%Vor%

Sie können auch die ReplacementNode -Definition bearbeiten, so dass die ID des Knotens, den sie ersetzt, beibehalten wird. (indem Sie nicht nur newNode zurückgeben, sondern stattdessen einen weiteren neuen Knoten mit dem value und getChildren des newNode zurückgeben, sondern den originalRefId des nodetoReplace )