f# - 我如何知道一个函数在 F# 中是否是尾递归的

Question

我写了以下函数:

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#)？

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

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

Answer 1

不幸的是，没有简单的方法。

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

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

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

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

tailcall func args

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

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

这是您询问的代码示例:

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