F# tail recursive call

.net, cil, f#, tail, tail-recursion

Solution

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

Problem

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?

Original source