Ich versuche den Verzeichnisbaum zu durchqueren. Ein naives Tiefen-zuerst-Traversal scheint die Daten nicht auf eine faule Art und Weise zu erzeugen und nicht genug Speicher zu haben. Als nächstes probierte ich einen breiten ersten Ansatz, der das gleiche Problem zeigt - er nutzt den gesamten verfügbaren Speicher und stürzt dann ab.
Der Code, den ich habe, ist:
%Vor%Ich denke, dass der gesamte Code entweder linear oder tail rekursiv ist, und ich erwarte, dass die Auflistung von Dateinamen sofort beginnt, aber tatsächlich nicht. Wo ist der Fehler in meinem Code und meinem Denken? Wo habe ich faule Bewertung verloren?
Ich werde drei verschiedene Tricks verwenden, um deine Frage zu lösen.
pipes , um Dateinamen gleichzeitig mit dem Durchsuchen der Struktur zu streamen. StateT (Seq FilePath) , um eine Breite-zuerst-Traversierung zu erreichen. MaybeT , um eine manuelle Rekursion beim Schreiben der Schleife und beim Beenden zu vermeiden. Der folgende Code kombiniert diese drei Tricks in einem Monaden-Transformatorstapel.
%Vor%Dies erzeugt einen Generator von Breiten-zuerst-Dateinamen, die gleichzeitig mit der Baumdurchquerung konsumiert werden können. Sie konsumieren die Werte mit:
%Vor%Sie können sogar festlegen, dass nicht alle Werte angefordert werden:
%Vor%Noch wichtiger ist, dass das letzte Beispiel den Baum nur so weit durchquert, wie es notwendig ist, um die drei Dateien zu erzeugen, und dann wird es aufhören. Dies verhindert, dass verschwenderisch den gesamten Baum durchquert wird, wenn alles, was Sie wollten, 3 Ergebnisse war!
Um mehr über den Trick mit pipes library zu erfahren, konsultiere das Pipes Tutorial bei Control.Pipes.Tutorial .
Um mehr über den Loop-Trick zu erfahren, lesen Sie diesen Blogpost .
Ich konnte keinen guten Link für den Warteschlangentrick für die erste Traversierung finden, aber ich weiß, dass er irgendwo da draußen ist. Wenn jemand anders einen guten Link dafür kennt, bearbeite einfach meine Antwort, um sie hinzuzufügen.
Ich habe die Verwaltung der Pipe und die Traversierung der Bäume getrennt. hier zuerst der Code für die Pipe (im Wesentlichen der Code von Gonzales - danke!):
%Vor%Als nächstes der Code für die Baumdurchquerung:
%Vor%Ich hoffe, doBF durch eine ähnliche Funktion zu ersetzen, um zuerst die Tiefe zu durchlaufen. Ich nahm an, dass ich traverseTree allgemeiner und nicht nur für FilePath ~ String machen könnte, aber ich sehe nicht, in welcher Klasse die leere Funktion auf Sequenzen ist. könnte allgemein nützlich sein.
Tags und Links haskell