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#)?
我怎么知道f#编译器是否把它变成了一个循环?有没有不用Reflector就能找到答案(我没有使用Reflector的经验,也不知道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...
此外,f# std lib中是否有一个函数可以多次运行给定的函数,每次都将最后的输出作为输入?假设我有一个字符串,我想在字符串上运行一个函数然后再在合成字符串上运行它,等等。
2 个解决方案
#1
22
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.)
f#编译器将为所有尾部调用生成.tail IL指令(除非使用了关闭它们的编译器标志——当您希望保留堆栈帧进行调试时使用),但是直接尾部递归函数将被优化为循环。(编辑:我认为现在f#编译器在通过这个调用站点证明没有递归循环的情况下也不能发出。tail;鉴于.tail操作码在许多平台上的速度稍慢,这是一种优化。
'tailcall' is a reserved keyword, with the idea that a future version of F# may allow you to write e.g.
“tailcall”是一个保留的关键字,它的意思是,未来的f#版本可能会让你写出类似这样的句子。
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
#2
2
I like the rule of thumb Paul Graham formulates in On Lisp: if there is work left to do, e.g. manipulating the recursive call output, then the call is not tail recursive.
我喜欢Paul Graham在Lisp中提出的经验法则:如果还有工作要做,例如操作递归调用输出,那么调用不是尾递归的。
#1
22
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.)
f#编译器将为所有尾部调用生成.tail IL指令(除非使用了关闭它们的编译器标志——当您希望保留堆栈帧进行调试时使用),但是直接尾部递归函数将被优化为循环。(编辑:我认为现在f#编译器在通过这个调用站点证明没有递归循环的情况下也不能发出。tail;鉴于.tail操作码在许多平台上的速度稍慢,这是一种优化。
'tailcall' is a reserved keyword, with the idea that a future version of F# may allow you to write e.g.
“tailcall”是一个保留的关键字,它的意思是,未来的f#版本可能会让你写出类似这样的句子。
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
#2
2
I like the rule of thumb Paul Graham formulates in On Lisp: if there is work left to do, e.g. manipulating the recursive call output, then the call is not tail recursive.
我喜欢Paul Graham在Lisp中提出的经验法则:如果还有工作要做,例如操作递归调用输出,那么调用不是尾递归的。