F# F# Performance Tips and Tricks Using tail-recursion for efficient iteration
Example
Coming from imperative languages many developers wonder how to write a for-loop that exits early as F# doesn't support break, continue or return.
The answer in F# is to use tail-recursion which is a flexible
and idiomatic way to iterate while still providing excellent performance.
Say we want to implement tryFind for List. If F# supported return we would write tryFind a bit like this:
let tryFind predicate vs =
for v in vs do
if predicate v then
return Some v
None
This doesn't work in F#. Instead we write the function using tail-recursion:
let tryFind predicate vs =
let rec loop = function
| v::vs -> if predicate v then
Some v
else
loop vs
| _ -> None
loop vs
Tail-recursion is performant in F# because when the F# compiler detects that a function is tail-recursive it rewrites
the recursion into an efficient while-loop. Using ILSpy we can see that this is true for our function loop:
internal static FSharpOption<a> loop@3-10<a>(FSharpFunc<a, bool> predicate, FSharpList<a> _arg1)
{
while (_arg1.TailOrNull != null)
{
FSharpList<a> fSharpList = _arg1;
FSharpList<a> vs = fSharpList.TailOrNull;
a v = fSharpList.HeadOrDefault;
if (predicate.Invoke(v))
{
return FSharpOption<a>.Some(v);
}
FSharpFunc<a, bool> arg_2D_0 = predicate;
_arg1 = vs;
predicate = arg_2D_0;
}
return null;
}
Apart from some unnecessary assignments (which hopefully the JIT-er eliminates) this is essentially an efficient loop.
In addition, tail-recursion is idiomatic for F# as it allows us to avoid mutable state.
Consider a sum function that sums all elements in a List. An obvious first try would be this:
let sum vs =
let mutable s = LanguagePrimitives.GenericZero
for v in vs do
s <- s + v
s
If we rewrite the loop into tail-recursion we can avoid the mutable state:
let sum vs =
let rec loop s = function
| v::vs -> loop (s + v) vs
| _ -> s
loop LanguagePrimitives.GenericZero vs
For efficiency the F# compiler transforms this into a while-loop that uses mutable state.
