Search code examples
f#tail-recursiontail-call

When executed will this be a tail call?


Once compiled and ran will this behave as a tail call?

let rec f accu = function
   | [] -> accu
   | h::t -> (h + accu) |> f <| t

Maybe there is an easy way to test behavior that I'm not aware of, but that might be another question.


Solution

  • I think this is much easier to see if you do not use the pipelining operator. In fact, the two pipelining operators are defined as inline, so the compiler will simplify the code to the following (and I think this version is also more readable and simpler to understand, so I would write this):

    let rec f accu = function
       | [] -> accu
       | h::t -> f (h + accu) t
    

    Now, you can read the definition of tail-call on Wikipedia, which says:

    A tail call is a subroutine call that happens inside another procedure as its final action; it may produce a return value which is then immediately returned by the calling procedure.

    So yes, the call to f on the last line is a tail-call.

    If you wanted to analyze the original expression (h + accu) |> f <| t (without knowing that the pipelining operators are inlined), then this actually becomes ((h + accu) |> f) <| t. This means that the expression calls the <| operator with two arguments and returns the result - so the call to <| is a tail call.

    The <| operator is defined like this:

    let (<|) f a = f a
    

    Now, the call to f inside the pipelining operator is also a tail-call (and similarly for the other pipelining operator).

    In summary, if the compiler did not do inlining, you would have a sequence of three tail-calls (compiled using the .NET .tail instruction to make sure that .NET performs a tail-call). However, since the compiler performs inlining, it will see that you have a recursive tail-call (f calling f) and this can be more efficiently compiled into a loop. (But calls across multiple functions or operators cannot use loops that easily.)