Um Clojure zu lernen, löse ich die Probleme bei 4Urlaub . Ich schneide mir gerade die Zähne bei der Frage 164 , wo Sie (teilweise) die Sprache a DFA akzeptiert. Eine interessante Bedingung ist, dass die Sprache unendlich sein kann, also muss die Lösung faul sein (in diesem Fall die Testfälle für die Lösung (take 2000 ... .
Ich habe eine Lösung, die auf meiner Maschine funktioniert, aber wenn ich sie auf der Website einreiche, bläst sie den Stack (wenn ich die Anzahl der akzeptablen Strings von 2000 auf 20000 erhöhe, blase ich den Stack auch lokal, also ist es ein Mangel an meiner Lösung).
Meine Lösung [1] ist:
%Vor%akzeptiert das DFA
%Vor% und gibt die Sprache zurück, die DFA akzeptiert ( #{a ab abc} ). Bei der Ermittlung der ersten 2000 akzeptierten DFA-Zeichenfolgen
es bläst den Stapel. Natürlich sollte ich die Lösung so umstrukturieren, dass sie rekursiv ist, aber ich sehe nicht, wie das möglich ist. Insbesondere sehe ich nicht, wie es überhaupt möglich ist, Faulheit mit Schwanz-Rekursivität zu kombinieren (über recur oder trampoline ). Die Funktion lazy-seq erstellt einen Abschluss, sodass die Verwendung von recur in lazy-seq den Abschluss als Rekursionspunkt verwendet. Bei der Verwendung von lazy-seq in recur wird immer lazy-seq ausgewertet, weil recur einen Funktionsaufruf ausgibt, der seine Argumente auswerten muss.
Wenn ich trampoline verwende, sehe ich nicht, wie ich iterativ eine Liste konstruieren kann, deren Elemente lazy evaluiert werden können. Wie ich es benutzt habe und es benutzt sehe, kann trampoline nur dann einen Wert zurückgeben, wenn es fertig ist (d. H. Eine der Trampolining-Funktionen gibt keine Funktion zurück).
Ich betrachte eine andere Art der Lösung dieses Problems, die nicht in den Rahmen dieser Frage fällt. Ich arbeite gerade an einer Lösung, die iterate verwendet, wobei jeder Schritt nur die Zeichenfolgen berechnet, die der "nächste Schritt" (folgende Übergänge vom aktuellen Status) akzeptiert, so dass er überhaupt nicht rekurriert. Sie verfolgen dann nur die aktuellen Zustände und die Strings, die Sie in diesen Zustand gebracht haben (die Präfixe für die nächsten Zustände). In diesem Fall ist es schwierig, zu erkennen, wann ein DFA, der eine endliche Sprache akzeptiert, keine Ergebnisse mehr zurückgibt. Ich habe noch kein richtiges Stop-Kriterium für das take-while um das iterate entwickelt, aber ich bin mir ziemlich sicher, dass ich es schaffen werde, dass diese Lösung funktioniert. Für diese Frage interessiert mich die grundsätzliche Frage: Können Faulheit und Schwanzrekursivität kombiniert werden oder ist das grundsätzlich unmöglich?
[1] Beachten Sie, dass es auf der Seite einige Einschränkungen gibt, wie zB def und defn nicht verwenden zu können, was einige Besonderheiten meines Codes erklären könnte.
Das Problem ist, dass Sie etwas bauen, das wie folgt aussieht:
%Vor%Was im Prinzip gut ist, aber die Elemente auf der rechten Seite dieser Liste werden für eine lange Zeit nicht realisiert, und bis Sie sie realisieren, haben sie einen riesigen Stapel von faulen Sequenzen, die es sein müssen gezwungen, um ein einzelnes Element zu erhalten.
Wenn Ihnen ein Spoiler nichts ausmacht, können Sie meine Lösung unter Ссылка sehen. Ich mache zwei Dinge anders als du, und beide sind wichtig:
doall , um eine Sequenz zu erzwingen, die ich träge aufbaue. Da ich weiß, dass viele concat s einen sehr großen Stack erstellen, und ich weiß auch, dass die Sequenz niemals unendlich sein wird, erzwinge ich die ganze Sache, während ich sie erstelle, um die Layerung von lazy Sequenzen zu verhindern, die den Stack überlaufen lässt. Bearbeiten: Im Allgemeinen können Sie keine Lazy-Sequenzen mit Tail-Rekursion kombinieren. Sie können eine Funktion verwenden, die beide verwendet, die möglicherweise wiederkehrend ist, wenn vor dem Hinzufügen eines einzelnen Elements mehr Arbeit zu erledigen ist, und die bei einem neuen Element immer wiederkehren, aber meistens haben sie entgegengesetzte Ziele und versuchen zu kombinieren sie werden unvorsichtig nur zu Schmerzen führen und keine besonderen Verbesserungen.
Wenn Sie lazy-seq verwenden, führen Sie einfach einen normalen Funktionsaufruf aus, anstatt recur zu verwenden. Die Faulheit vermeidet den rekursiven Stackverbrauch, für den sonst recur verwendet wird.
Zum Beispiel eine vereinfachte Version von repeat :
Tags und Links clojure lazy-evaluation stack-overflow