Head, Tail, and Null

The null function

The function null tests whether a list is empty using pattern matching:

let null = function
  | [] -> true
  | x :: l -> false
(* val null : 'a list -> bool = <fun> *)

The two clauses match the two possible forms of a list: empty ([]) or non-empty (x :: l). The function returns true only for the empty list.

Head and tail access

hd returns the first element of a non-empty list; tl returns the list of remaining elements:

let hd (x :: l) = x
(* val hd : 'a list -> 'a = <fun> *)

let tl (x :: l) = l
(* val tl : 'a list -> 'a list = <fun> *)

Both functions raise a warning when compiled: the pattern matching is not exhaustive — the case [] is not handled. Applying hd or tl to [] raises an exception at runtime. The fix is to use null to check for emptiness beforehand, or better, to use proper two-case pattern matching.

Partial match warnings

OCaml’s compiler detects incomplete pattern matches. Two faulty declarations illustrate the problem:

(* Handles only empty lists -- non-empty case missing *)
let rec nlength [] = 0

(* Handles only non-empty lists -- empty case missing *)
let rec nlength (x :: xs) = 1 + nlength xs

These are two separate declarations. The second let replaces the first rather than extending it. To handle both cases, use the function keyword with | to separate clauses.

Polymorphic types

The primitive list functions have polymorphic types using type variables:

Function	Type	Meaning
null	'a list -> bool	Works on any list
hd	'a list -> 'a	Head matches element type
tl	'a list -> 'a list	Tail is same type of list

The symbols 'a and 'b are type variables (pronounced “alpha”, “beta”, etc.) and stand for any type. Code using these functions is checked for type correctness at compile time, and this guarantees that at run time, all elements of a list have the same type.

Pattern matching over hd and tl

Taking a list apart using combinations of hd and tl is hard to get right and seldom necessary. Pattern matching with the function keyword is the preferred approach:

let rec process = function
  | [] -> base_case
  | x :: xs -> ... x ... process xs ...

This is safer (no missing cases if both are covered) and clearer (the structure of the list is visible in the pattern).