HR F#: List Length

The problem List Length is interesting because it can be solved using mutable counter but it also can be solved in more functional way.

Count the number of elements in an array without using count, size or length operators (or their equivalents).

First, let's see on the solution using mutable variable:

let len lst =
  let mutable index = 0
  for _ in lst do
    index <- index + 1

The real challenge here is to implement it without using mutable state. The common way to do so is to use recursion and pattern matching:

let rec len lst =
    match lst with
    | [ ] -> 0
    | [ _ ] -> 1
    | _ :: tail -> 1 + len tail

While matching the lst first matched with empty list, then with list containing one argument, and then with list containing more than one argument. On the match it extracts tail (all elements except first) and applies len to it.