f# - 执行时这将是尾调用吗？

Question

一旦编译并运行，这会表现为尾调用吗？

let rec f accu = function
   | [] -> accu
   | h::t -> (h + accu) |> f <| t

也许有一种简单的方法可以测试我不知道的行为，但这可能是另一个问题。

Answer 1

我认为如果您不使用流水线操作符，这更容易看出。其实这两个流水线操作符被定义为inline，所以编译器会把代码简化成下面这样（而且我觉得这个版本也更易读、更容易理解，所以我就这么写）：

let rec f accu = function
   | [] -> accu
   | h::t -> f (h + accu) t

现在，您可以在 Wikipedia 上阅读 tail-call的定义，其中说：

尾调用是在另一个过程中作为其最终动作发生的子例程调用；它可能会产生一个返回值，然后由调用过程立即返回。

所以是的，f最后一行的调用是尾调用。

如果您想分析原始表达式(h + accu) |> f <| t（不知道流水线操作符是内联的），那么这实际上变成了((h + accu) |> f) <| t. 这意味着表达式<|使用两个参数调用运算符并返回结果 - 所以调用<|是尾调用。

<|运算符定义如下：

let (<|) f a = f a

现在，对f流水线操作符内部的调用也是尾调用（对于其他流水线操作符也是如此）。

总而言之，如果编译器不进行内联，您将拥有一系列三个尾调用（使用 .NET.tail指令编译以确保 .NET 执行尾调用）。然而，由于编译器执行内联，它会看到你有一个递归尾调用（f调用f），这可以更有效地编译成一个循环。（但是跨多个函数或运算符的调用不能那么容易地使用循环。）

Answer 2

如果您在此处查看答案，您会注意到它f <| t与（仅当您将需要括号 f t的表达式代替时才会有所不同）。t

同样x |> y是一样的y x。

这会产生一个看起来像这样的等效表达式：f (h + accu) t，所以（假设编译器没有错误或类似的错误），您的函数应该是尾递归的，并且很可能会被编译成某种循环。