F#尾递归调用

Question

我有这段代码：

let rec collect ( t : BCFile list ) ( acc : Set<BCFile> ) : Set<BCFile> =
    match t with
    | [] -> acc
    | hr::tl -> collect ( tl ) ( Set.union acc ( FindSourceFilesForTarget ( hr ) ) )
let s = collect (Set.toList targets) Set.empty

看起来应该是尾递归，但实际上不是（查看IL代码）。有任何想法为什么没有编译成尾递归？

- phwp

---

你是在发布模式下编译吗？只有在发布模式下，尾调用才会被优化。 - N_A

Answer 1

据我所知，collect函数实际上是尾递归的。第一个情况明显地只返回acc。第二个情况首先调用FindSourceFilesForTarget，然后调用Set.union，最后返回。你可以按照以下方式重写它（这更清楚地显示了尾递归）：

| hr::tl -> 
    let sources = FindSourceFilesForTarget hr
    let acc = Set.union acc sources
    collect tl

因为这只是一个调用自身的单一函数，编译器将其优化为循环。这是编译后代码的样子（当您使用反射器将其转换为C#时）:

public static FSharpSet<int> collect(FSharpList<int> t, FSharpSet<int> acc) {
  while (true) {
    FSharpList<int> fSharpList = t;
    if (fSharpList.TailOrNull == null) break;
    // The following corresponds to the second case 
    FSharpList<int> tl = fSharpList.TailOrNull;
    int hr = fSharpList.HeadOrDefault;
    // Variables 'acc' and 't' are mutated (instead of calling the function)
    acc = SetModule.Union<int>(acc, Program.FindSourceFilesForTarget<int>(hr));
    t = tl;
  }
  return acc;
}

稍微离题了一点，你也可以使用标准库函数来表示这个：

t |> Seq.map FindSourceFilesForTarget |> Set.unionMany

- Tomas Petricek

---

谢谢你的回答。另外一个问题是，如果使用unionMany，管道会在可用时立即开始合并集合，还是等到收集前一个管道步骤（在这种情况下为“Seq.map FindSourceFilesForTarget”）的所有输出后再开始？我之所以进行递归调用，是为了在集合变得可用时对它们进行联合，因为它们具有大量相同的数据和大量迭代（数十万次），所以我不想缓存所有结果，并希望尽快丢弃重复项。 - phwp

当t是一个惰性数据源(IEnumerable)时，unionMany操作应该按需读取它们(因此FindSourceFilesForTarget也将按需评估)。因此我认为，在这种情况下，整个数据集不会在途中加载到内存中。 - Tomas Petricek