Skip to content
Tutorials Center
My learning

Topics

Lesson 17 of 40 ยท Lists, Arrays and Records

Lists in OCaml

Master OCaml's immutable singly linked lists: list literals, the :: and @ operators, pattern matching on lists, recursion over lists and the cost of common operations.

The list is the workhorse data structure of OCaml. It is an immutable, singly linked sequence of values that all have the same type. Almost every OCaml program uses lists, and understanding how they are built is the key to pattern matching and recursion.

Creating lists

OCAML
# [1; 2; 3];;
- : int list = [1; 2; 3]
# ["a"; "b"];;
- : string list = ["a"; "b"]
# [];;
- : 'a list = []
# [[1; 2]; [3]];;
- : int list list = [[1; 2]; [3]]

Elements are separated by semicolons, not commas. This is the most common beginner error:

OCAML
# [1, 2, 3];;
- : (int * int * int) list = [(1, 2, 3)]

With commas you build a list of one tuple. Remember: ; between list elements, , between tuple components.

All elements must have the same type, so [1; "two"] is a type error. The empty list [] is polymorphic: 'a list.

Ranges are not built in, but easy to write; recent versions of the standard library have List.init:

OCAML
# List.init 5 (fun i -> i * i);;
- : int list = [0; 1; 4; 9; 16]

Cons and append

Two operators build lists:

  • x :: xs ("cons") puts x in front of the list xs.
  • xs @ ys joins two lists.
OCAML
# 0 :: [1; 2];;
- : int list = [0; 1; 2]
# [1; 2] @ [3; 4];;
- : int list = [1; 2; 3; 4]

In fact [1; 2; 3] is shorthand for 1 :: 2 :: 3 :: [], and :: associates to the right. Every list is either the empty list [] or a head x and a tail xs joined by ::. That structure is the entire definition of the type.

A list is a chain of cells

Head The first element
Tail The rest, another list
Empty [] ends every list

[1; 2; 3] is 1 :: 2 :: 3 :: []

1 / 2

Immutability and sharing

A list never changes. 0 :: xs creates one new cell that points to the existing xs; the old list is untouched and shared.

OCAML
let xs = [2; 3]
let ys = 1 :: xs
let zs = 0 :: xs      (* xs is shared by ys and zs *)

That is why consing is O(1), while @ copies its left operand, costing O(length of left list). Appending in a loop is a classic way to make code quadratic. Prefer to cons and reverse at the end.

Pattern matching on lists

A list is [] or x :: rest, so those two patterns cover all cases:

OCAML
let rec length = function
  | [] -> 0
  | _ :: rest -> 1 + length rest

Patterns can look deeper:

OCAML
let describe = function
  | [] -> "empty"
  | [x] -> "one element: " ^ string_of_int x
  | [x; y] -> "two elements: " ^ string_of_int (x + y)
  | x :: _ :: _ :: _ -> "three or more, starting with " ^ string_of_int x

The compiler checks the match is exhaustive. If you forget a case it warns you (and the toplevel names the missing pattern):

OCAML
let head = function
  | x :: _ -> x
(* Warning: this pattern-matching is not exhaustive.
   Here is an example of a case that is not matched: [] *)

If a function should fail on [], it is better to return an option or raise a named exception on purpose than to leave it silent.

Recursion on lists

The pattern for most list functions:

OCAML
let rec sum = function
  | [] -> 0
  | x :: rest -> x + sum rest

let rec append a b =
  match a with
  | [] -> b
  | x :: rest -> x :: append rest b

let rec reverse_onto acc = function
  | [] -> acc
  | x :: rest -> reverse_onto (x :: acc) rest

let reverse lst = reverse_onto [] lst
OCAML
# reverse [1; 2; 3];;
- : int list = [3; 2; 1]

Using two elements at a time, consider a function that checks sortedness:

OCAML
let rec is_sorted = function
  | [] | [_] -> true
  | a :: (b :: _ as rest) -> a <= b && is_sorted rest

The a :: (b :: _ as rest) pattern names the whole tail as rest while also looking inside it. | combines patterns ([] | [_]).

Common list operations and their costs

Operation Cost Note
x :: xs O(1) cheapest
List.hd xs / List.tl xs O(1) raise on empty
List.length xs O(n) not stored
xs @ ys O(length xs) copies left list
List.nth xs i O(i) no random access
List.rev xs O(n)

If you need fast random access or many updates, use an array, or a Map/Hashtbl. If you mostly add and remove at the front, lists are perfect.

Lists versus other languages

There is no list.append(x) that mutates. Instead, you build new lists and let older versions be garbage collected. This feels odd at first but removes a whole category of aliasing bugs, and it makes lists safe to share between functions and threads.

A stand-in: lists as head and tail

The stand-in represents a list as null or { head, tail }, exactly like OCaml's cells, and shows that consing shares the tail.

JS Stand-in: cons cells and sharing

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is [1, 2, 3] in OCaml?

    Commas build tuples. Lists use semicolons, so [1, 2, 3] is [(1, 2, 3)].
  2. 2. What does 0 :: [1; 2] evaluate to?

    :: adds an element at the front.
  3. 3. Why is xs @ ys more expensive than x :: xs?

    @ must rebuild every cell of its left operand; the right list is shared.
  4. 4. Which two patterns cover every list?

    A list is either empty or a head consed onto a tail.

Summary

  • Lists are immutable singly linked cells of one element type: [1; 2; 3].
  • :: conses in O(1); @ appends in O(length of the left list).
  • Match on [] and x :: rest; the compiler checks exhaustiveness.
  • Use semicolons between elements, not commas.
  • Consing shares structure; build in reverse and List.rev when needed.

Next: The List module