我如何知道一个函数在 F# 中是否是尾递归的 [英] How do I know if a function is tail recursive in F#

问题描述

我写了以下函数:

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

我如何知道 F# 编译器是否将其转换为循环?有没有不使用 Reflector 的方法(我没有使用 Reflector 的经验，也不懂 C#)?

How can I know if the F# compiler turned it into a loop? Is there a way to find out without using Reflector (I have no experience with Reflector and I Don't know C#)?

另外，是否可以在不使用内部函数的情况下编写尾递归函数，或者循环是否必须驻留在其中?

Also, is it possible to write a tail recursive function without using an inner function, or is it necessary for the loop to reside in?

此外，F# std lib 中是否有一个函数可以多次运行给定的函数，每次都将最后一个输出作为输入?假设我有一个字符串，我想在字符串上运行一个函数，然后在结果字符串上再次运行它，依此类推...

Also, Is there a function in F# std lib to run a given function a number of times, each time giving it the last output as input? Lets say I have a string, I want to run a function over the string then run it again over the resultant string and so on...

推荐答案

不幸的是没有简单的方法.

Unfortunately there is no trivial way.

阅读源代码并使用类型并通过检查确定某事是否是尾调用并不太难(它是最后一件事"，而不是在尝试"块中)，但人们其次-猜测自己并犯错.没有简单的自动化方法(例如检查生成的代码除外).

It is not too hard to read the source code and use the types and determine whether something is a tail call by inspection (is it 'the last thing', and not in a 'try' block), but people second-guess themselves and make mistakes. There's no simple automated way (other than e.g. inspecting the generated code).

当然，你可以在大量的测试数据上尝试你的函数，看看它是否会爆炸.

Of course, you can just try your function on a large piece of test data and see if it blows up or not.

F# 编译器将为所有尾调用生成 .tail IL 指令(除非使用编译器标志来关闭它们 - 用于当您想要保留堆栈帧以进行调试时)，直接尾递归函数除外将被优化为循环.(我认为现在 F# 编译器也无法发出 .tail 在它可以证明没有递归循环通过这个调用站点的情况下；这是一种优化，因为 .tail 操作码在许多平台上有点慢.)

The F# compiler will generate .tail IL instructions for all tail calls (unless the compiler flags to turn them off is used - used for when you want to keep stack frames for debugging), with the exception that directly tail-recursive functions will be optimized into loops. ( I think nowadays the F# compiler also fails to emit .tail in cases where it can prove there are no recursive loops through this call site; this is an optimization given that the .tail opcode is a little slower on many platforms.)

'tailcall' 是一个保留关键字，其想法是未来版本的 F# 可能允许您编写例如

'tailcall' is a reserved keyword, with the idea that a future version of F# may allow you to write e.g.

tailcall func args

然后如果不是尾调用，则会收到警告/错误.

and then get a warning/error if it's not a tail call.

只有那些不是自然尾递归的函数(因此需要一个额外的累加器参数)才会强迫"你进入内部函数"习语.

Only functions that are not naturally tail-recursive (and thus need an extra accumulator parameter) will 'force' you into the 'inner function' idiom.

这是您询问的代码示例:

Here's a code sample of what you asked:

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

这篇关于我如何知道一个函数在 F# 中是否是尾递归的的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！