Iterate efficiently in F# using tail-recursion

tailrec.md

Coming from imperative languages many developers wonder how to write a for-loop the exits early as F# doesn't support break, continue nor return. The answer in F# is to use tail-recursion which is a more flexible and idiomatic way to iterate while still providing excellent performance.

Say we like 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 detect that a function is tail-recursive it rewrites the recursion into an efficient while-loop. Using ILSpy can we see that this is true for 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 "interesting" assignments (which hopefully the JIT:er eliminates) this is essentially an efficient loop.

In addition tail-recursion is more idiomatic 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.