使用尾递归进行有效迭代

来自命令式语言的许多开发人员想知道如何编写一个提前退出的 for-loop，因为 F# 不支持 break，continue 或 return。F# 中的答案是使用尾递归 ，这是一种灵活且惯用的迭代方式，同时仍然提供出色的性能。

假设我们想为 List 实施 tryFind。如果 F# 支持 return，我们会像这样写一下 tryFind：

let tryFind predicate vs =
  for v in vs do
    if predicate v then
      return Some v
  None

这在 F# 中不起作用。相反，我们使用 tail-recursion 编写函数：

let tryFind predicate vs =
  let rec loop = function
    | v::vs -> if predicate v then 
                   Some v 
               else 
                   loop vs
    | _ -> None
  loop vs

尾递归在 tihuan 13 中是有效的，因为当 F# 编译器检测到函数是尾递归时，它会将递归重写为有效的 while-loop。使用 ILSpy，我们可以看到这对于我们的函数 loop 来说是正确的：

internal static FSharpOption<a> loop@3-10<a>(FSharpFunc<a, bool> predicate, FSharpList<a> _arg1)
{
  while (_arg1.TailOrNull != null)
  {
    FSharpList<a> fSharpList = _arg1;
    FSharpList<a> vs = fSharpList.TailOrNull;
    a v = fSharpList.HeadOrDefault;
    if (predicate.Invoke(v))
    {
      return FSharpOption<a>.Some(v);
    }
    FSharpFunc<a, bool> arg_2D_0 = predicate;
    _arg1 = vs;
    predicate = arg_2D_0;
  }
  return null;
}

除了一些不必要的任务（希望 JIT-er 消除），这本质上是一个有效的循环。

另外，尾递归对于 F# 是惯用的，因为它允许我们避免可变状态。考虑一个 sum 函数，它总结了 List 中的所有元素。一个明显的第一次尝试是这样的：

let sum vs =
  let mutable s = LanguagePrimitives.GenericZero
  for v in vs do
    s <- s + v
  s

如果我们将循环重写为尾递归，我们可以避免可变状态：

let sum vs =
  let rec loop s = function
    | v::vs -> loop (s + v) vs
    | _ -> s
  loop LanguagePrimitives.GenericZero vs

为了提高效率，F# 编译器将其转换为使用可变状态的 while-loop。