Louis Wasserman hat die aktuellen Implementierungen von inits und tails in Data.Sequence geschrieben. Er weist darauf hin, dass sie sehr effizient sind, und wenn man sich den Code anschaut, kann ich sehen, dass alles, was sie tun, sauber und von oben nach unten läuft, was zu guten Leistungen für faule Bäume führt. Leider kann ich nicht wirklich Kopf oder Zahl davon machen, was sie gerade machen. Kann mir jemand helfen? Der Code ist ein bisschen lang, aber kann auf Hackage .
Ich bin es!
Ich denke, der beste Ansatz ist wahrscheinlich, ein Beispiel zu erarbeiten. Lass uns gehen ...
%Vor%Hier ist eine Sequenz, etwas vereinfacht (z. B. die Elem-Wrapper auslassen).
Lassen Sie uns in diesem Zusammenhang handeln; Schwänze sind im Wesentlichen symmetrisch. Unser rekursiver Algorithmus wird die leere Init auslassen und nur nichtleere Dinge einschließen.
Präfix
Also wird die Präfixziffer von inits mit im wesentlichen fmap digitToTree (initsDigit (Two 1 2)) erzeugt.
Das sind also die ersten beiden Eingänge des Ganzen, und diese Ziffer wird die Präfixziffer des Ergebnisses von inits sein. (Abgesehen davon, dass wir die leere Sequenz voranstellen werden, nachdem wir fertig sind, aber lasst uns das jetzt ignorieren.)
Innerer Baum
Nehmen wir nun die Eingänge des inneren Baums, die als FingerTree (Node a) behandelt werden - wir werden die Knoten noch nicht auseinanderziehen, es ist nur ein Zwei-Element FingerTree mit zwei Knoten. Ich werde nicht die Details dazu machen, es wird nur durch den gleichen Algorithmus rekursiv, ich werde einfach magisch das Ergebnis erreichen
Das sind also die Eingänge des inneren Baumes. Wie stimmen diese mit den Inits des äußeren Baumes überein? Jede Init des inneren Baums entspricht einem Baum, der
enthältTwo 1 2
Node der Init des inneren Baums Node der Init des inneren Baums So wird jedes FingerTree (Node a) , das durch eine Init des inneren Baums gewonnen wurde, auf ein Node (FingerTree a) abgebildet, das ein FingerTree für jede Init des letzten Knotens in FingerTree (Node a) enthält.
Zum Beispiel wird Single (Node2 3 4) mit dem letzten extrahierten Knoten in Empty und Node2 3 4 zerlegt, und die resultierende Node (FingerTree a) ist
Und für das andere Präfix des inneren Baums, Deep (One (Node2 3 4)) Empty (One (Node2 5 6)) , ergibt das Extrahieren des letzten Node den Rest Single (Node2 3 4) und den extrahierten Knoten Node2 5 6 , also den resultierenden 'Knoten (FingerTree a)
Das ist also eine Operation, die ein FingerTree (Node a) , eine einzelne Init des inneren Baums, zu einem Node (FingerTree a) führt. Wenn wir also die Inits des inneren Baums rekursiv als FingerTree (FingerTree (Node a)) erfasst haben, ordnen wir diese Funktion ihnen zu, um ein FingerTree (Node (FingerTree a)) zu erhalten, was genau das ist, was wir wollten; es ist der innere Baum der Innereien des Ganzen.
Suffix
Schließlich gibt es Einträge des ursprünglichen Baums, die aus
bestehen und diese werden die Suffixziffer des Baumes von inits. initsDigit (Two 7 8) gibt Two (One 7) (Two 7 8) zurück, und wir ordnen im Wesentlichen nur \sf -> Deep pr m sf zu, um
Also, das ist nicht so, wie der Code organisiert ist. Wir haben eine Funktion von FingerTree a bis FingerTree (FingerTree a) beschrieben, aber die tatsächliche Implementierung ist im Wesentlichen die plus fmap , weil wir die Elemente immer irgendwie zuordnen müssen - selbst wenn sie nur neue Typen umhüllen. Aber das machen wir im Grunde.
Tags und Links haskell data-structures sequence