我怎么知道函数是否在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'是一个保留关键字,其想法是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