Learn

OCaml lists are linked lists, immutable, homogeneous (all elements same type). Combined with pattern matching and recursion, they're the central data structure for functional OCaml.

Creating lists

let empty = []
let xs = [1; 2; 3]                  (* semicolons, NOT commas *)
let ys = 0 :: xs                    (* 0 prepended; xs unchanged *)

The :: operator is cons — adds an element to the front. Cheap (O(1)). Lists are built tail-first.

1 :: 2 :: 3 :: []                   (* same as [1; 2; 3] *)

A list is either empty [] or head :: tail.

Pattern matching on lists

let rec length xs =
  match xs with
  | [] -> 0
  | _ :: rest -> 1 + length rest

let rec sum xs =
  match xs with
  | [] -> 0
  | x :: rest -> x + sum rest

The _ is a wildcard — "any value, don't bind it." Always handle both [] (empty) and x :: rest (non-empty) — exhaustiveness check warns if missing.

Tail recursion

Naive sum above is NOT tail-recursive — the addition happens AFTER the recursive call. For huge lists, switch to the accumulator pattern:

let sum xs =
  let rec loop acc = function
    | [] -> acc
    | x :: rest -> loop (acc + x) rest
  in
  loop 0 xs

The recursive call is the LAST operation. OCaml optimizes this to a loop with no stack growth.

function is shorthand for fun x -> match x with — saves typing.

Common list operations

List.length [1; 2; 3]              (* 3 *)
List.rev [1; 2; 3]                  (* [3; 2; 1] *)
List.map (fun x -> x * 2) [1; 2; 3] (* [2; 4; 6] *)
List.filter (fun x -> x > 2) [1; 2; 3; 4]  (* [3; 4] *)
List.fold_left (+) 0 [1; 2; 3]      (* 6 *)
List.fold_right (+) [1; 2; 3] 0     (* 6 *)
List.iter print_int [1; 2; 3]       (* prints 123 *)
List.mem 2 [1; 2; 3]                 (* true *)
List.nth [10; 20; 30] 1              (* 20 — 0-indexed *)
List.append [1; 2] [3; 4]            (* [1; 2; 3; 4]; or use @ *)
List.concat [[1]; [2]; [3]]          (* [1; 2; 3] *)
List.find (fun x -> x > 2) [1; 2; 3] (* 3 *)
List.exists (fun x -> x > 5) [1; 2]  (* false *)
List.for_all (fun x -> x > 0) [1; 2] (* true *)
List.sort compare [3; 1; 2]          (* [1; 2; 3] *)

The @ operator concatenates lists. It's O(n) in the LEFT operand — xs @ [x] traverses xs every time. Build with :: and reverse if needed.

fold_left vs fold_right

List.fold_left (fun acc x -> acc + x) 0 [1; 2; 3]
(* ((0 + 1) + 2) + 3 = 6 *)

List.fold_right (fun x acc -> x + acc) [1; 2; 3] 0
(* 1 + (2 + (3 + 0)) = 6 *)

fold_left is tail-recursive (constant stack); fold_right isn't (uses stack proportional to list length). For numeric folds on large lists, fold_left.

Argument order differs between them — fold_left takes (acc, elem); fold_right takes (elem, acc). Easy to swap by accident.

Common mistakes

• Using commas instead of semicolons — [1, 2, 3] is a TUPLE wrapped in a list (length 1!), not three elements. Use semicolons.
• Non-tail-recursive list traversals — stack overflow on long lists. Use accumulator pattern.
• xs @ [x] in a loop — O(n²). Build with :: and reverse at the end.
• Forgetting rec for recursive functions — without it, OCaml looks for an existing function; you get a name resolution error.
• Mixing list types — lists are HOMOGENEOUS. [1; "a"] is a type error.