OCaml Pattern Matching Recursive list processing with pattern matching

Example

Here we demonstrate how to process lists recursively using OCaml's pattern matching syntax.

let rec map f lst =
  match lst with
  | [] -> []
  | hd::tl -> (f hd)::(map f tl)

In this case, the pattern [] matches the empty list, while hd::tl matches any list that has at least one element, and will assign the first element of the list to hd and the rest of the list (could be empty) to tl.

Note that hd::tl is a very general pattern and will match any list that isn't empty. We can also write patterns that match on lists with a specific number of elements:

(* Return the last element of a list. Fails if the list is empty. *)
let rec last lst =
  match lst with
  | [] -> failwith "Empty list"
  | [x] -> x (* Equivalent to x::[], [x] matches a list with only one element *)
  | hd::tl -> last tl

(* The second to last element of a list. *)
let rec second_to_last lst =
  match lst with
  | [] -> failwith "Empty list"
  | x::[] -> failwith "Singleton list"
  | fst::snd::[] -> snd
  | hd::tl -> second_to_last tl

Additionally, OCaml supports pattern matching on the elements of lists themselves. We can be more specific about the structure of elements inside a list, and OCaml will infer the correct function type:

(* Assuming a list of tuples, return a list with first element of each tuple. *)
let rec first_elements lst =
  match lst with
  | [] -> []
  | (a, b)::tl -> a::(first_elements tl)
(* val first_elements : ('a * 'b) list -> 'a list = <fun> *)

By combining these patterns together, we can process any arbitrarily complex list.