Ich versuche, Brians Fold for Bianary Trees ( Ссылка ) anzupassen gelten für Multiway-Bäume.
Zusammenfassung von Brians Blog:
Datenstruktur:
%Vor%Binäre Baumfaltungsfunktion
%Vor%Beispiele
%Vor%Multiway Tree Version [nicht (vollständig) funktioniert] :
Datenstruktur
%Vor%Faltfunktion
%Vor%Beispiel 1 Rückgabe 28 - scheint zu funktionieren
%Vor%Beispiel 2
Wird nicht ausgeführt
%Vor% Anfangs dachte ich, dass% code% ein MFoldTree benötigt, aber ich habe es stattdessen mit dem Operator map.something arbeiten lassen.
Jede Hilfe im zweiten Beispiel und / oder die Korrektur, was ich in der Funktion @ gemacht habe, wäre großartig!
Prost
dusiod
Eine andere Lösung könnte
sein %Vor%wirklich, wir können Baum als eine lineare Struktur behandeln (um ihn zu falten).
Anwendungsfall
%Vor% Der Filter ist derselbe wie bei normaler Faltung (weil mfold eine normale Falte ist):
Diese Funktion könnte generisch sein (als List.fold , Array.fold , ... könnten Generika sein).
"aber die Absicht der zweiten ist, den gesamten modifizierten Baum zurückzugeben, so dass alle Knoten, die zum Beispiel den Wert 6 hatten, jetzt den Wert 0 haben"
Aber das ist keine fold Berechnung, ist ein map !
Sie können es einfach machen (wiederum als lineare Struktur behandeln)
%Vor%Anwendungsfall
%Vor% Ich schlage vor, dies für jeden möglichen Listencontainer zu tun ( Seq , List , Array , ...), es ermöglicht dem Benutzer, die beste Strategie im Kontext auszuwählen.
Anmerkungen:
Der Trick ist, dass Sie eine zusätzliche Funktion zum Falten übergeben müssen.
In der Brian-Version nimmt die Faltfunktion nur nodeF , das mit dem Wert im Knoten und den beiden Werten aus den linken und rechten Unterbäumen aufgerufen wird.
Das ist nicht ausreichend für Mehrwegebäume. Hier benötigen wir eine Funktion nodeF , die mit dem Wert im Knoten aufgerufen wird, und das Ergebnis, das durch Aggregieren aller Werte der Unterbäume erzeugt wird. Aber Sie brauchen auch eine Funktion - sagen wir combineF , die den Wert kombiniert, der von mehreren Unterbäumen eines Knotens erzeugt wird.
Ihre Faltfunktion ist ein guter Anfang - Sie müssen nur einen weiteren rekursiven Aufruf hinzufügen, um tail :
Die Summierung ist einfach, weil wir einfach den Operator + für beide Funktionen verwenden:
Das Filtern des Baumes ist komplizierter. Die Funktion nodeF ruft das Element im Knoten und eine Liste von untergeordneten Knoten ab (das ist das Ergebnis der Aggregation) und erzeugt einen einzelnen -Knoten. Die combineF -Funktion erhält das Ergebnis von einem ersten Knoten (das ist ein MultiTree -Wert) und eine Liste von Kindern, die von den verbleibenden Knoten erzeugt wurden. Der Anfangswert, der von einem leeren Baum erzeugt wird, ist eine leere Liste:
Tags und Links f# tree traversal fold multiway-tree