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