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