f# recursion tail-recursion tail-call-optimization

F# 中如何知道函数是否尾递归

发布于 2024-07-18 05:31:06 字数 450 浏览 7 评论 0原文

我编写了以下函数：

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 中是否有一个函数可以多次运行给定函数，每次都将最后的输出作为输入？假设我有一个字符串，我想在该字符串上运行一个函数，然后在结果字符串上再次运行它，依此类推......

原文

I wrote the follwing function:

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

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

Edit: 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?

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...

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

丶情人眼里出诗心の 2024-07-25 05:31:06

编辑：从 F# 8 开始，有一种使用 [] 属性的方法，请参阅此答案： https://stackoverflow.com/a/77532717/969070

原始答案：

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

阅读源代码并使用类型并通过检查确定某些内容是否是尾调用（它是“最后一件事”，而不是在“try”块中）并不太难，但是人们会事后猜测自己和犯错误。没有简单的自动化方法（除了检查生成的代码之外）。

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

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

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

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

Edit: Since F# 8 there is a way with the [<TailCall>] attribute, see this answer: https://stackoverflow.com/a/77532717/969070

Original answer:

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.

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. (EDIT: 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' 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

回复收藏 0 原文

勿挽旧人 2024-07-25 05:31:06

从 F# 8 开始，编译器可以为您检查这一点！使用 TailCallAttribute 标记该函数，如果您提供非尾递归的实现，您将收到警告。

例如，以下代码：

[<TailCall>]
let rec fibNaive n =
    if n <= 1 then n
    else fibNaive (n - 1) + fibNaive (n - 2)

发出两个警告 FS3569 实例：成员或函数“fibNaive”具有“TailCallAttribute”属性，但未以尾递归方式使用。（每个递归一个）虽然

此代码不会发出警告：

[<TailCall>]
let fibFast n =
    let rec fibFast x y n =
        match n with
        | _ when n < 1 -> x
        | 1 -> y
        | _ -> fibFast y (x + y) (n - 1)
    fibFast 0 1 n

为了获得奖励积分，最好将 FS3569 添加到您的 fsproj，从而将其转变为错误。

The compiler can check this for you, as of F# 8! Mark the function with TailCallAttribute, and you'll get a warning if you provide an implementation that isn't tail recursive.

For example, this code:

[<TailCall>]
let rec fibNaive n =
    if n <= 1 then n
    else fibNaive (n - 1) + fibNaive (n - 2)

emits two instances of Warning FS3569 : The member or function 'fibNaive' has the 'TailCallAttribute' attribute, but is not being used in a tail recursive way. (one for each recursive call)

While this code emits no warnings:

[<TailCall>]
let fibFast n =
    let rec fibFast x y n =
        match n with
        | _ when n < 1 -> x
        | 1 -> y
        | _ -> fibFast y (x + y) (n - 1)
    fibFast 0 1 n

For bonus points, it can be a good idea to turn this into an error, by adding <WarningsAsErrors>FS3569</WarningsAsErrors> to your fsproj.

回复收藏 0 原文