Offenlegung: Dies kam in FsCheck, einem F # Random Testing Framework, das ich behalte. Ich habe eine Lösung, aber ich mag sie nicht. Außerdem verstehe ich das Problem nicht - es wurde lediglich umgangen.
Eine ziemlich standardisierte Implementierung von (monadisch, wenn wir große Wörter verwenden) ist:
%Vor%Dabei kann gen durch einen Berechnungsgenerator der Wahl ersetzt werden. Leider verbraucht diese Implementierung Stack-Speicherplatz, und so stapeln Stapelüberläufe, wenn die Liste lang genug ist. Die Frage ist: Warum? Ich weiß im Prinzip foldBack ist nicht tail rekursiv, aber die cleveren Hasen des F # -Teams haben das in der foldBack-Implementierung umgangen. Gibt es ein Problem in der Implementierung des Berechnungsherstellers?
Wenn ich die Implementierung nach unten ändere, ist alles in Ordnung:
%Vor% Der Generator für Gen-Typ und -Bearbeitung kann der Vollständigkeit halber in der FsCheck-Quelle
Aufbauend auf Tomas 'Antwort definieren wir zwei Module:
%Vor%Um die Dinge etwas zu vereinfachen, schreiben wir Ihre ursprüngliche Sequenzfunktion als
um %Vor% Jetzt wird sequence [for i in 1 .. 100000 -> unit i] vollständig ausgeführt, unabhängig davon, ob sequence in Kurt.gen oder Tomas.gen definiert ist. Das Problem besteht nicht darin, dass sequence einen Stapelüberlauf verursacht, wenn Sie Ihre Definitionen verwenden. Die Funktion, die vom Aufruf von sequence zurückgegeben wird, verursacht einen Stapelüberlauf, wenn it aufgerufen wird.
Um zu sehen, warum dies so ist, erweitern wir die Definition von sequence in Bezug auf die zugrunde liegenden monadischen Operationen:
Indem wir die Werte Kurt.unit und Kurt.bind einbinden und wie verrückt vereinfachen, erhalten wir
Nun ist es hoffentlich klar, warum Aufruf von let (Kurt.Gen f) = sequence [for i in 1 .. 1000000 -> unit i] in f 0 den Stack überläuft: f erfordert einen nicht-tail-rekursiven Aufruf zur Sequenz und Auswertung der resultierenden Funktion, so dass es für jeden rekursiven Aufruf einen Stack-Frame gibt.
Wenn Sie stattdessen Tomas.unit und Tomas.bind in die Definition von sequence einfügen, erhalten wir die folgende vereinfachte Version:
Das Nachdenken über diese Variante ist schwierig. Sie können empirisch verifizieren, dass es den Stapel für einige beliebig große Eingaben nicht durchbrennen wird (wie Tomas in seiner Antwort zeigt), und Sie können durch die Auswertung gehen, um sich selbst von dieser Tatsache zu überzeugen. Der Stack-Verbrauch hängt jedoch von den Gen -Instanzen in der übergebenen Liste ab, und es ist möglich, den Stack für Eingaben zu verwenden, die selbst nicht tail-rekursiv sind:
Sie haben Recht - der Grund, warum Sie einen Stack-Überlauf bekommen, ist, dass die bind -Operation der Monade tail-rekursiv sein muss (weil sie verwendet wird, um Werte während des Faltens zu aggregieren).
Die in FsCheck verwendete Monade ist im Wesentlichen eine Zustands-Monade (sie enthält den aktuellen Generator und einige Zahlen). Ich habe es ein wenig vereinfacht und habe etwas wie:
%Vor% Hier ist die Funktion bind nicht tail-rekursiv, weil sie k aufruft und dann noch mehr Arbeit leistet. Sie können die Monade als Fortsetzungsmonade ändern. Es wird als eine Funktion implementiert, die den Status und eine Fortsetzung - eine Funktion, die mit dem Ergebnis als Argument aufgerufen wird, übernimmt. Für diese Monade können Sie bind tail rekursiv machen:
Das folgende Beispiel stapelt den Überlauf nicht (und tat dies mit der ursprünglichen Implementierung):
%Vor%Tags und Links f# tail-recursion tail-call-optimization