Wie erkenne ich, ob eine Funktion Schwanz rekursiv in F # ist

ich die follwing Funktion schrieb:Wie erkenne ich, ob eine Funktion Schwanz rekursiv in F # ist

let str2lst str = 
    let rec f s acc = 
     match s with 
     | "" -> acc 
     | _ -> f (s.Substring 1) (s.[0]::acc) 
    f str []

Wie kann ich wissen, ob die F # -Compiler es in eine Schleife gedreht? Gibt es eine Möglichkeit, es herauszufinden, ohne Reflektor zu benutzen (ich habe keine Erfahrung mit Reflektoren und ich kenne C# nicht)?

Edit: Ist es auch möglich, eine Tail-rekursive Funktion zu schreiben, ohne eine innere Funktion zu benutzen, oder ist es notwendig, dass die Schleife sich befindet?

Gibt es auch eine Funktion in F # std lib, um eine bestimmte Funktion mehrmals auszuführen und jedes Mal die letzte Ausgabe als Eingabe zu geben? Sagen wir, ich habe eine Zeichenkette, ich möchte eine Funktion über die Zeichenkette ausführen und sie dann erneut über die resultierende Zeichenkette usw. ausführen ...

Quelle

2009-04-30 Dave Berk

Siehe auch http://stackoverflow.com/questions/5809683/is-my-rec-function-tail-recursive – Brian

Leider gibt es keine triviale Möglichkeit.

Es ist nicht zu schwer, den Quellcode zu lesen und die Typen zu verwenden und zu bestimmen, ob etwas ein Tail-Call durch Inspektion ist (ist es "das letzte Ding" und nicht in einem "Versuch" -Block), sondern Menschen an zweiter Stelle -glauben sich selbst und machen Fehler. Es gibt keinen einfachen automatisierten Weg (außer beispielsweise den generierten Code zu inspizieren).

Natürlich können Sie einfach Ihre Funktion auf einem großen Stück Testdaten versuchen und sehen, ob es explodiert oder nicht.

Der F # -Compiler generiert .tail-IL-Anweisungen für alle Tailaufrufe (sofern nicht die Compilerflags zum Deaktivieren verwendet werden - werden verwendet, wenn Stackframes zum Debuggen beibehalten werden sollen), mit Ausnahme von Tail-rekursiv Funktionen werden in Schleifen optimiert. (EDIT: Ich denke heutzutage, dass der F # -Compiler in Fällen, in denen es keine rekursiven Schleifen durch diese Call-Site gibt, keine .tail ausgeben kann. Dies ist eine Optimierung, da der .tail-Opcode auf vielen Plattformen etwas langsamer ist.)

'tailcall' ist ein reserviertes Schlüsselwort, mit der Idee, dass eine zukünftige Version von F # Ihnen erlauben könnte, zB zu schreiben

tailcall func args

und dann eine Warnung/einen Fehler erhalten, wenn es sich nicht um ein Tail Call handelt.

Nur Funktionen, die nicht von Natur aus tail-rekursiv sind (und daher einen zusätzlichen Akkumulator-Parameter benötigen) werden Sie in das Idiom "innere Funktion" "zwingen".

Hier ist ein Beispiel für den Code, was Sie gefragt:

let rec nTimes n f x = 
    if n = 0 then 
     x 
    else 
     nTimes (n-1) f (f x) 

let r = nTimes 3 (fun s -> s^" is a rose") "A rose" 
printfn "%s" r

Quelle

2009-04-30 13:23:42 Brian

"tailcall" ist interessant, wie Sie die Stelle des Anrufs anstelle von was ein a sein kann nützlichere "tailrec" -Deklaration für die gesamte Funktion. Kannst du eine "tail rekursive" Funktion haben? –

@StephenSwensen Sie können absolut. Kontrollfluss-Zweige könnten zu einer Alternative zwischen einem Tail-Aufruf und einem Aufruf führen, der kein Tail-Aufruf ist, und Sie möchten möglicherweise nur denjenigen überprüfen, der tatsächlich ein Tail-Aufruf zur Kompilierungszeit ist. 'lek recf x = wenn x> 0, dann f (1 + x) else 0 + f (1 + x)' illustriert das Konzept, obwohl es offensichtlich nicht enden würde. –

ich die Faustregel gilt: Paul Graham in Auf Lisp formuliert mag: wenn es Arbeit, zum Beispiel mehr zu tun manipuliert die rekursive Aufrufausgabe, dann ist der Aufruf nicht tail rekursiv.

Quelle

2012-04-17 11:48:44 vemv

Wie erkenne ich, ob eine Funktion Schwanz rekursiv in F # ist

Antwort

Verwandte Themen