Reference solution:

let rec last l =
  match l with
  | [] -> None
  | [x] -> Some x
  | _ :: xs -> last xs

Three shapes: the empty list (no last element), a one-element list (that element is the last), and a longer list (drop the head and recurse). The [x] clause must come before the _ :: xs clause, since a singleton also matches _ :: xs.

Reference solution:

let rec nth l n =
  match l with
  | [] -> None
  | x :: rest -> if n = 0 then Some x else nth rest (n - 1)

Walk down the list and the index together: when n reaches 0 the head is the answer; otherwise drop the head and look for position n - 1 in the tail. Running off the end of the list (the [] clause) means n was too big.

Reference solution:

let rec count_occurrences x l =
  match l with
  | [] -> 0
  | y :: ys ->
      (if x = y then 1 else 0) + count_occurrences x ys

The empty list contributes nothing. For a cons, add 1 when the head equals x (and 0 otherwise), then recurse on the tail. The comparison x = y is OCaml's structural equality, so this works for any type whose values can be compared with =.

Reference solution:

let rec take n l =
  match l with
  | [] -> []
  | _ when n <= 0 -> []
  | x :: rest -> x :: take (n - 1) rest

Two ways to stop: the list runs out ([]), or we have taken enough (n <= 0, expressed as a guard). Otherwise keep the head and take n - 1 from the tail. The guarded clause sits before the x :: rest clause so that n <= 0 wins even on a non-empty list.

Reference solution:

let rec drop n l =
  match l with
  | [] -> []
  | _ when n <= 0 -> l
  | _ :: rest -> drop (n - 1) rest

Mirror of take: when n <= 0 we are done dropping and return the list unchanged; otherwise discard the head and drop n - 1 more. Note the guarded clause returns l (the whole remaining list), not [].

Reference solution:

let rec is_sorted l =
  match l with
  | [] | [_] -> true
  | x :: (y :: _ as rest) -> x <= y && is_sorted rest

An or-pattern handles the two "trivially sorted" shapes together: [] and a singleton [_]. For a list with at least two elements, name the head x, the second element y, and (with as) the whole tail rest; the list is sorted when x <= y and the tail is sorted. Binding the tail with as lets us recurse on it without rebuilding y :: ....

Reference solution:

let rec merge xs ys =
  match xs, ys with
  | [], _ -> ys
  | _, [] -> xs
  | x :: xs', y :: ys' ->
      if x <= y then x :: merge xs' ys
      else y :: merge xs ys'

Match on the pair of lists. If either is empty, the answer is the other. Otherwise compare the two heads: emit the smaller one and recurse, advancing only the list it came from. Using <= (not <) keeps equal elements in a stable order and handles duplicates.

Reference solution:

let rec sum_tree t =
  match t with
  | Leaf -> 0
  | Node (l, v, r) -> sum_tree l + v + sum_tree r

A Leaf holds nothing, so it sums to 0. A Node contributes its own value v plus the sums of both subtrees. The two recursive calls mirror the two subtrees: this is the tree version of summing a list.

Reference solution:

let rec tree_max t =
  match t with
  | Leaf -> None
  | Node (l, v, r) ->
      let best a b =
        match a, b with
        | None, o | o, None -> o
        | Some x, Some y -> Some (if x > y then x else y)
      in
      best (Some v) (best (tree_max l) (tree_max r))

A Leaf has no maximum (None). For a Node, the answer is the largest of v, the left maximum, and the right maximum, each of which is an int option. The local helper best merges two options: if one is None the other wins (the or-pattern None, o | o, None), and when both are Some it keeps the larger.

Reference solution:

let rec tree_contains x t =
  match t with
  | Leaf -> false
  | Node (l, v, r) ->
      v = x || tree_contains x l || tree_contains x r

An empty tree contains nothing. A node contains x if its own value matches, or if either subtree contains it. The || operator short-circuits, so once the value is found the remaining subtrees are not searched. (This is an arbitrary tree; it does not assume the ordering of a search tree.)

Reference solution:

let beats a b =
  match a, b with
  | Rock, Scissors | Paper, Rock | Scissors, Paper -> true
  | _ -> false

Match on the pair a, b. An or-pattern lists the three winning combinations on a single clause; the wildcard _ catches every other pair (losses and ties) and returns false. Without the three winning pairs spelled out, you would need a clause per case; the or-pattern keeps it to two clauses.

Reference solution:

let rec to_int n =
  match n with
  | Zero -> 0
  | Succ m -> 1 + to_int m

let rec add a b =
  match a with
  | Zero -> b
  | Succ m -> Succ (add m b)

to_int peels one Succ at a time, adding 1 for each, until it reaches Zero. add recurses on its first argument: adding Zero to b gives b, and adding Succ m to b is one more than adding m to b, i.e. Succ (add m b). This is addition defined purely by pattern matching on the structure of a number.