使用尾遞迴進行有效迭代

來自命令式語言的許多開發人員想知道如何編寫一個提前退出的 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。