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).知道为什么它不编译使用尾递归？

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