CODEWITHSUNDEEP
f#tail-recursiontail-call
Iter
Iter

Reputation: 361

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.

Upvotes: 2

Views: 147

Answers (2)

Tomas Petricek
Tomas Petricek

Reputation: 243096

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.)

Upvotes: 6

N_A
N_A

Reputation: 19897

If you look at the answer here, you will notice that f <| t is the same as f t (it only makes a difference if you put an expression in place of t which requires parenthesis).

Likewise x |> y is the same as y x.

This results in an equivalent expression which looks like this: f (h + accu) t, So (assuming the compiler doesn't have a bug or some such), your function should be tail recursive and most likely will be compiled down to a loop of some sort.

Upvotes: 2

Related Questions