F# tail recursive call

Question

I have this code:

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

It looks like it should be tail recursive, but it is not (looking at IL). Any idea why it is not compiled to use tail recursion?

Answer 1

As far as I can tell, the collect function actually is tail-recursive. The first case clearly just returns the acc. The second case first invokes FindSourceFilesForTarget, then calls Set.union and then returns. You could rewrite it as follows (which shows the tail-recursion more clearly):

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

Because this is just a single function calling itself, the compiler optimizes it into a loop. This is how the compiled code looks (when you use reflector to turn it to 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;
}

On a slightly unrelated note, you could also express this using standard library functions:

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