F# 使用尾递归进行有效的迭代

示例

从命令式语言未来许多开发商不知道怎么写了for-loop退出事件早F#不支持break，continue或者return。答案F#是使用尾递归，这是一种灵活且惯用的迭代方式，同时仍提供出色的性能。

假设我们要实现tryFind的List。如果F#支持的话，return我们可以这样写tryFind：

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

这不适用于F#。相反，我们使用尾递归编写函数：

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

尾递归是有效的，F#因为当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
  loopLanguagePrimitives.GenericZerovs

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