OCaml Module 5 – Lists, higher-order functions and laziness

Lists and list patterns

Build OCaml lists with [], :: and @, take them apart with patterns, choose between _opt and raising functions, and use association lists for small lookups.

Beginner
10 minutes
Examples run with ocaml 5.5.1, opam 2.6.0, dune 3.24.2 and Python 3.14.8
By MySmartCoPilot

Free: the whole lesson. With a pass: the model answers to its 2 interview questions.

What you will learn

Construct lists with [], :: and @, and state what each one costs
Write recursive list functions with [] and x :: rest patterns
Choose between the List functions that raise and their _opt partners
Use association lists for small lookups and predict which binding a lookup finds

Before you start

Variants, options and recursive types

What you’ll learn · Before you start

What you will learn

Construct lists with [], :: and @, and state what each one costs
Write recursive list functions with [] and x :: rest patterns
Choose between the List functions that raise and their _opt partners
Use association lists for small lookups and predict which binding a lookup finds

Before you start

Variants, options and recursive types

On this page

Building a list of 10,000 numbers by adding each one at the end with @ allocated 150,015,000 words of memory, while adding each at the front with :: and reversing once allocated 60,000. The two lists are equal; the cost differs about 2,500 times because an OCaml list is built from the front, one cell at a time, and a cell never changes.

You will build lists with [], :: and @ and say what each costs, and write list functions whose patterns follow the two shapes every list has, [] and x :: rest. You will also choose between the functions that raise an exception and their _opt partners, and look up keys in an association list.

A list is a chain of cells, built from the front

[1; 2; 3] is a shorter way to write 1 :: 2 :: 3 :: []. A list is either empty, [], or a value joined to a list by ::, which is read “cons”. Each :: makes one cons cell: One link of an OCaml list, built by x :: tail: it holds a value, the head, and the rest of the list, the tail. A cell never changes, so lists can share their tails.: a value, the head, and the list after it, the tail. Every element has the same type, so [1; "two"] was refused, and a cell can never be changed after it is built. That is what lets two lists share cells. Step through the session’s lists:

Interactive · step by step Which cells a new list builds and which it shares Step through the session's four lists. Names are on the left; each box on the right is one cell, a value and the list after it.

The drawing shows the whole scene; its 6 steps are listed below.

Every step as text

let l = [2; 3]. Two cells. The first holds 2 and points at the second, which holds 3 and ends the list with [].
let a = 1 :: l. One new cell holding 1, whose tail is the first cell of l. Nothing is copied, which is why List.tl a == l printed true.
let r = [4; 5]. Two more cells for r, built the same way from the front.
let m = l @ r. The cell holding 3 in l ends with [], but in m it must lead on to 4. A cell never changes, so @ builds a copy of each cell of l and points the last copy at r.
The right side is shared. The cells of r are not copied. List.tl (List.tl m) == r printed true, so m and r share the cells holding 4 and 5.
Old lists stay as they were. l still printed [2; 3]. No list can change, so sharing is always safe, and the cost of a new list is the cells it builds, one for :: and the whole left side for @.

Building lists with ::, sharing a tail, and @ Python · cons_session.py

from session import toplevel

# A list is [] or a value joined to a list with ::. Adding at the front builds one new cell and shares the rest; @
# copies every cell of its left side and shares its right side, which == (the same cell in memory) shows.
toplevel("""
1 :: 2 :: 3 :: [];;
let l = [2; 3];;
let a = 1 :: l;;
List.tl a == l;;
let r = [4; 5];;
let m = l @ r;;
List.tl (List.tl m) == r;;
l;;
[[1; 2]; []; [3]];;
[1; "two"];;
""")

Output

$ ocaml
OCaml version 5.5.1
Enter #help;; for help.

# 1 :: 2 :: 3 :: [];;
- : int list = [1; 2; 3]
# let l = [2; 3];;
val l : int list = [2; 3]
# let a = 1 :: l;;
val a : int list = [1; 2; 3]
# List.tl a == l;;
- : bool = true
# let r = [4; 5];;
val r : int list = [4; 5]
# let m = l @ r;;
val m : int list = [2; 3; 4; 5]
# List.tl (List.tl m) == r;;
- : bool = true
# l;;
- : int list = [2; 3]
# [[1; 2]; []; [3]];;
- : int list list = [[1; 2]; []; [3]]
# [1; "two"];;
Line 1, characters 4-9:
1 | [1; "two"];;
        ^^^^^
Error: This constant has type string but an expression was expected of type
         int

Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 cons_session.py

let a = 1 :: l built one cell and pointed it at l, so List.tl a == l was true: the == test asks whether two values are the same cells in memory. l @ r could not do the same with l. The cell holding 3 ends l, and in the joined list it must lead on to 4, so @ copied both cells of l and shared all of r, which List.tl (List.tl m) == r confirmed. l itself still printed [2; 3].

You write	New cells built	Shared with an older list
`x :: l`	1	all of `l`
`l1 @ l2`	one per element of `l1`	all of `l2`
`List.rev l`	one per element of `l`	nothing

The cost shows when a list is built in a loop. The program below builds the numbers 0 to n − 1 twice, once with i :: acc and a single List.rev at the end, once with acc @ [i], and counts the words each allocation took:

Building n numbers from the front and from the back, counted in words Python · cost_session.py

from session import run, write

# The cost of building a list of n numbers two ways, counted in words allocated (Gc.minor_words): consing at the front
# and reversing once, or appending each number at the end with @, which copies the whole list built so far every time.
# The last line checks that both ways build the same list.
write("cost.ml", """let n = int_of_string Sys.argv.(1)

let front () =
  let rec go acc i = if i = n then List.rev acc else go (i :: acc) (i + 1) in
  go [] 0

let back () =
  let rec go acc i = if i = n then acc else go (acc @ [i]) (i + 1) in
  go [] 0

let words f =
  let before = Gc.minor_words () in
  let l = f () in
  (List.length l, Gc.minor_words () -. before)

let () =
  let n1, w1 = words front and n2, w2 = words back in
  Printf.printf "n = %d: :: then List.rev: %d elements, %.0f words\\n" n n1 w1;
  Printf.printf "n = %d: acc @ [i] each time: %d elements, %.0f words\\n" n n2 w2;
  Printf.printf "n = %d: the same list both ways: %b\\n" n (front () = back ())
""")
run("""
ocamlopt cost.ml -o cost
./cost 1000
./cost 10000
""")

Output

$ ocamlopt cost.ml -o cost
$ ./cost 1000
n = 1000: :: then List.rev: 1000 elements, 6000 words
n = 1000: acc @ [i] each time: 1000 elements, 1501500 words
n = 1000: the same list both ways: true
$ ./cost 10000
n = 10000: :: then List.rev: 10000 elements, 60000 words
n = 10000: acc @ [i] each time: 10000 elements, 150015000 words
n = 10000: the same list both ways: true

Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 cost_session.py

A cell takes three words, a one-word header and its two fields, the head and the tail, so the front version allocated exactly 6 words an element: 6,000 for 1,000 numbers and 60,000 for 10,000. The back version copies the whole list on every step, 1 + 2 + … + n cells in all, and allocated 1,501,500 words for 1,000 numbers and 150,015,000 for 10,000: ten times the input, a hundred times the work. Both versions built the same list, as the last line of each run says.

Appending one element at a time

Wrong: go (acc @ [x]) rest for every element, which copies acc each time. Right: go (x :: acc) rest, then List.rev acc once at the end, or let List.map or List.filter build the list in order for you.

List.rev is cheap enough to call once: it walks the list a single time and builds one cell per element, which is the second half of the 6 words.

Key idea

Adding at the front builds one cell and shares the rest; @ copies its whole left side. Build lists from the front and reverse once.

Patterns follow the two shapes a list can have

Every list is [] or x :: rest, so a function on lists has a case for each, and the second case usually calls the function again on rest. sum returned 0 for [] and x + sum rest otherwise, and gave 12 for [3; 4; 5]. Patterns can also name more than one element: [x] matches a list of exactly one, [_; _] a list of exactly two, and x :: (y :: _ as rest) a list of two or more, binding the tail that starts at y to rest:

sum, last, pairs and a match on the length of a list Python · patterns_session.py

from session import toplevel

# A list function has a case for [] and a case for x :: rest, the two shapes a list can have. Longer patterns name
# more elements, and a match that forgets [] draws warning 8 and then raises Match_failure on the empty list.
toplevel("""
let rec sum = function [] -> 0 | x :: rest -> x + sum rest;;
sum [3; 4; 5];;
let rec last = function [] -> None | [x] -> Some x | _ :: rest -> last rest;;
(last [7; 8; 9], last []);;
let rec pairs = function x :: (y :: _ as rest) -> (x, y) :: pairs rest | _ -> [];;
pairs [1; 2; 3; 4];;
let describe = function [] -> "empty" | [_] -> "one" | [_; _] -> "two" | _ -> "many";;
List.map describe [[]; [5]; [5; 6]; [5; 6; 7]];;
let first = function x :: _ -> x;;
first [];;
""")

Output

$ ocaml
OCaml version 5.5.1
Enter #help;; for help.

# let rec sum = function [] -> 0 | x :: rest -> x + sum rest;;
val sum : int list -> int = <fun>
# sum [3; 4; 5];;
- : int = 12
# let rec last = function [] -> None | [x] -> Some x | _ :: rest -> last rest;;
val last : 'a list -> 'a option = <fun>
# (last [7; 8; 9], last []);;
- : int option * 'a option = (Some 9, None)
# let rec pairs = function x :: (y :: _ as rest) -> (x, y) :: pairs rest | _ -> [];;
val pairs : 'a list -> ('a * 'a) list = <fun>
# pairs [1; 2; 3; 4];;
- : (int * int) list = [(1, 2); (2, 3); (3, 4)]
# let describe = function [] -> "empty" | [_] -> "one" | [_; _] -> "two" | _ -> "many";;
val describe : 'a list -> string = <fun>
# List.map describe [[]; [5]; [5; 6]; [5; 6; 7]];;
- : string list = ["empty"; "one"; "two"; "many"]
# let first = function x :: _ -> x;;
Line 1, characters 12-32:
1 | let first = function x :: _ -> x;;
                ^^^^^^^^^^^^^^^^^^^^
Warning 8 [partial-match]: this pattern-matching is not exhaustive.
  Here is an example of a case that is not matched: []

val first : 'a list -> 'a = <fun>
# first [];;
Exception: Match_failure ("//toplevel//", 1, 12).

Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 patterns_session.py

last returned Some 9 for [7; 8; 9] and None for [], so the empty list has an answer instead of an error. pairs [1; 2; 3; 4] gave the three neighbouring pairs (1, 2), (2, 3) and (3, 4). describe told an empty list, one element, two and many apart with patterns alone. The order of cases matters: [x] comes before _ :: rest in last, because the broader pattern would also match a list of one.

The last function forgot the empty list. OCaml accepted first with “Warning 8 [partial-match]” and named [] as the case that is not matched, and the call first [] then raised Match_failure at run time.

Return an option when a list may be empty

A function such as last or first that has no answer for [] reads best with the type 'a list -> 'a option. The caller then handles the empty case where it knows what to do.

Checkpoint

Check: Cons cells, sharing and cost · List patterns and recursion

Question 1 of 2 xs is a list of 1,000 numbers. Which expression builds exactly one new cell?
Choose one answer.

List.rev xs xs @ [] xs @ [0] 0 :: xs

Show the answer: Question 1 of 2

Answer: 0 :: xs

Only a cell added at the front can share everything after it. The section's table says the same: x :: l builds 1 cell, l1 @ l2 one per element of l1, and List.rev l one per element of l.
Question 2 of 2 let second = function _ :: y :: _ -> y compiles with warning 8. What does second [5] do?
Choose one answer.

It is refused before it runs It raises Match_failure, because no case matches a list of one element It returns 5 It returns None

Show the answer: Question 2 of 2

Answer: It raises Match_failure, because no case matches a list of one element

A forgotten case compiles with warning 8 and fails only when a value reaches it. Add the missing cases, here [] and [_], or return an option, as last does.

Functions that may find nothing come in two forms

Some functions of the List module raise an exception when there is no answer. List.hd [] raised Failure "hd", List.nth [10; 20] 5 raised Failure "nth", a negative position raised Invalid_argument "List.nth", and List.find raised Not_found when no element passed its test. List.nth and List.find have partners whose names end in _opt and return an option: List.nth_opt [10; 20] 5 gave None, and so did List.find_opt, but a negative position is still an error for nth_opt. List.hd has none; a match with a [] case is its safe form. The session shows both kinds side by side, then functions that recent releases added:

Functions that raise, their _opt partners, and newer List functions Python · opt_session.py

from session import toplevel

# Some List functions raise an exception when there is no answer; their _opt partners return None instead (a negative
# position is still an error for nth_opt). The module also grew functions in recent releases: take and drop (5.3,
# negative counts allowed since 5.4), filter_mapi and split_map (5.5), and sort_uniq keeps the first of equal elements
# since 5.4.
toplevel("""
List.hd [];;
List.nth [10; 20] 5;;
List.nth_opt [10; 20] 5;;
List.nth [10; 20] (-1);;
List.nth_opt [10; 20] (-1);;
List.find (fun x -> x > 10) [3; 7];;
List.find_opt (fun x -> x > 10) [3; 7];;
List.find_index (fun x -> x > 5) [3; 7; 9];;
(List.take 2 [10; 20; 30], List.take (-1) [10; 20; 30], List.drop 5 [10; 20; 30]);;
List.filter_mapi (fun i x -> if i mod 2 = 0 then Some (x * 10) else None) [1; 2; 3; 4; 5];;
List.split_map (fun (name, marks) -> (name, marks >= 40)) [("asha", 72); ("ravi", 35)];;
List.sort_uniq (fun (a, _) (b, _) -> compare a b) [(1, "first"); (0, "z"); (1, "second")];;
""")

Output

$ ocaml
OCaml version 5.5.1
Enter #help;; for help.

# List.hd [];;
Exception: Failure "hd".
# List.nth [10; 20] 5;;
Exception: Failure "nth".
# List.nth_opt [10; 20] 5;;
- : int option = None
# List.nth [10; 20] (-1);;
Exception: Invalid_argument "List.nth".
# List.nth_opt [10; 20] (-1);;
Exception: Invalid_argument "List.nth".
# List.find (fun x -> x > 10) [3; 7];;
Exception: Not_found.
# List.find_opt (fun x -> x > 10) [3; 7];;
- : int option = None
# List.find_index (fun x -> x > 5) [3; 7; 9];;
- : int option = Some 1
# (List.take 2 [10; 20; 30], List.take (-1) [10; 20; 30], List.drop 5 [10; 20; 30]);;
- : int list * int list * int list = ([10; 20], [], [])
# List.filter_mapi (fun i x -> if i mod 2 = 0 then Some (x * 10) else None) [1; 2; 3; 4; 5];;
- : int list = [10; 30; 50]
# List.split_map (fun (name, marks) -> (name, marks >= 40)) [("asha", 72); ("ravi", 35)];;
- : string list * bool list = (["asha"; "ravi"], [true; false])
# List.sort_uniq (fun (a, _) (b, _) -> compare a b) [(1, "first"); (0, "z"); (1, "second")];;
- : (int * string) list = [(0, "z"); (1, "first")]

Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 opt_session.py

Choose by what an empty answer means. When a missing element is a normal outcome, such as a search the user typed, the _opt function makes the caller handle it. When it would mean a bug, the exception stops the program at the mistake. List.find_index returned Some 1, the position of 7, and List.take (-1) returned [] instead of raising. The module keeps growing, so check the release before you write a helper by hand:

Timeline · 8 events in order What the List module gained, release by release Walk through the releases in order. Before writing a list function by hand, check whether your compiler already has it.

4.05

The _opt partners safer lookups

nth_opt, find_opt and assoc_opt return None for a missing answer where nth, find and assoc raise an exception; a negative position still makes nth_opt raise Invalid_argument.
4.08

filter_map

filter_map applies a function that returns an option and keeps only the Some results, in one pass.
4.10

concat_map

concat_map applies a function that returns a list to every element and joins the results.
4.12

equal and compare

equal and compare compare two lists element by element with a function you pass, instead of the built-in comparison.
5.1

is_empty and find_index tail-recursive map

is_empty tests for [] and find_index returns the position of the first match as an option; map, filter, init and append became tail-recursive.
5.3

take, drop and their _while forms

take n and drop n split a list after n elements; take_while and drop_while split it where a test first fails.
5.4

singleton, safer take and drop changed behaviour

singleton x is [x]; take and drop accept a negative count instead of raising, and sort_uniq keeps the first of equal elements.
5.5

filter_mapi and split_map

filter_mapi passes each position to the function as well, and split_map maps every element to a pair and returns two lists.

take and drop in OCaml 5.3

List.take and List.drop arrived in OCaml 5.3, where a negative count raises Invalid_argument; from 5.4 a negative count takes nothing and drops nothing. List.filter_mapi and List.split_map need OCaml 5.5.

An association list is the simplest lookup table

A list of pairs, such as [("asha", 214); ("ravi", 305); ("meera", 118)], can map names to desk numbers. Such an association list: A list of (key, value) pairs used as a small lookup table; List.assoc returns the value of the leftmost pair whose key matches. needs no new type: List.assoc returns the value paired with a key, List.assoc_opt returns it as an option, and List.mem_assoc says whether the key is there:

Desk numbers in an association list Python · assoc_session.py

from session import toplevel

# An association list is a list of (key, value) pairs. Lookups walk it from the front, so the leftmost binding of a
# key wins: adding a pair at the front hides an older one without removing it.
toplevel("""
let desks = [("asha", 214); ("ravi", 305); ("meera", 118)];;
List.assoc "ravi" desks;;
List.assoc "kiran" desks;;
List.assoc_opt "kiran" desks;;
List.mem_assoc "meera" desks;;
let moved = ("ravi", 412) :: desks;;
(List.assoc "ravi" moved, List.length moved);;
List.remove_assoc "ravi" moved;;
List.map fst desks;;
""")

Output

$ ocaml
OCaml version 5.5.1
Enter #help;; for help.

# let desks = [("asha", 214); ("ravi", 305); ("meera", 118)];;
val desks : (string * int) list =
  [("asha", 214); ("ravi", 305); ("meera", 118)]
# List.assoc "ravi" desks;;
- : int = 305
# List.assoc "kiran" desks;;
Exception: Not_found.
# List.assoc_opt "kiran" desks;;
- : int option = None
# List.mem_assoc "meera" desks;;
- : bool = true
# let moved = ("ravi", 412) :: desks;;
val moved : (string * int) list =
  [("ravi", 412); ("asha", 214); ("ravi", 305); ("meera", 118)]
# (List.assoc "ravi" moved, List.length moved);;
- : int * int = (412, 4)
# List.remove_assoc "ravi" moved;;
- : (string * int) list = [("asha", 214); ("ravi", 305); ("meera", 118)]
# List.map fst desks;;
- : string list = ["asha"; "ravi"; "meera"]

Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 assoc_session.py

List.assoc "ravi" desks gave 305, and a missing name raised Not_found while assoc_opt gave None. A lookup walks the list from the front and stops at the first matching key. So ("ravi", 412) :: desks moved Ravi without removing his old pair: the lookup found 412, and the list had 4 pairs. List.remove_assoc removes only the first binding, which brought back 305.

Lookup	Gives for a missing key	Work for n pairs
`List.assoc k l`	exception `Not_found`	up to n comparisons
`List.assoc_opt k l`	`None`	up to n comparisons
`List.mem_assoc k l`	`false`	up to n comparisons

Every lookup may compare the key with every pair, so an association list suits a few dozen keys: settings, a small menu, test data. For thousands of keys, the standard library’s Map finds a key in time that grows with the logarithm of its size, and Hashtbl in about constant time; both come later in the track.

Checkpoint

Check: Raising functions and _opt partners · Association lists

Question 1 of 2 names is ["asha"; "ravi"]. Which call returns None instead of raising an exception?
Choose one answer.

List.find (fun s -> String.length s > 5) names List.nth names 2 List.hd (List.filter (fun s -> String.length s > 5) names) List.find_opt (fun s -> String.length s > 5) names

Show the answer: Question 1 of 2

Answer: List.find_opt (fun s -> String.length s > 5) names

nth, find and assoc each have an _opt partner. Use it when a missing answer is a normal outcome the caller must handle.
Question 2 of 2 prices is [("tea", 12); ("coffee", 20)], and prices2 is ("tea", 15) :: prices. What does (List.assoc "tea" prices2, List.length prices2) give?
Choose one answer.

(15, 3) (12, 3) An exception, because the key appears twice (15, 2)

Show the answer: Question 2 of 2

Answer: (15, 3)

Adding at the front hides an older binding without deleting it. List.remove_assoc "tea" prices2 would remove only the first pair and bring 12 back, as remove_assoc brought back Ravi's 305.

Practise: lists, patterns and lookups

The questions use the session’s lists, patterns and desk numbers with new values. Work out each result, the warning or the exception, before you check:

Interview questions

Warm-up (fresher to 2–5 years): why is adding to the front of an OCaml list cheap, while adding to the end is slow?

An OCaml list is a chain of immutable cells, each holding a value and the rest of the list. x :: l builds one new cell that points at the existing l, so it takes constant time and shares every cell of l. Adding at the end would change the last cell, which is not allowed, so l @ [x] copies every cell of l, time and memory in proportion to its length. In a loop that appends each new element, the copies add up to about n²/2 cells: 10,000 numbers took 150,015,000 words instead of 60,000. The usual pattern is to build the list backwards with :: and call List.rev once at the end.

Two harder questions follow: a report that slows down as rows are added, and an upload handler that stops on an empty file. For each, note what you would count or search for first, and hold that note against the question’s first step:

Model answers open with any pass: ₹79 for 1 week ($2.99), one payment that never renews.

Choose a pass

Fresher to mid

A report builder adds each row with rows := !rows @ [row]. With 2,000 rows it finishes at once; with 50,000 rows it runs for about half a minute and allocates billions of words. Explain the cost, and rewrite the loop so the time grows in step with the number of rows.

Model answer, Pro. Model answers open with any pass; prices are in the notice on this page. First step and follow-ups
Fresher to mid

An upload handler reads a file into a list of lines and calls List.hd lines to get the header row. An empty file stops it with Failure "hd" in production. Fix this case, and say how you would find similar calls before they fail.

Model answer, Pro. First step and follow-ups

Flashcards · 8 cards

Recall it, then check

Say the answer to yourself before you look: recalling it is what makes it stick.

What is an OCaml list built from?

Either [] or a value joined to a list with ::. Each :: builds one immutable cell, so the new list shares the tail it was built on.
What does l1 @ l2 copy, and what does appending one element at a time cost?

Every cell of l1, while l2 is shared, so appending element by element costs about n²/2 cells; consing with :: and one List.rev costs 2n.
How much memory did 10,000 numbers cost when appended with @, against consing and reversing once?

150,015,000 words with @ against 60,000 with :: and one List.rev: the same list, about 2,500 times the allocation.
Which two cases does every list function need, and what does a forgotten one cause?

[] and x :: rest; leaving out [] draws warning 8. Patterns such as [x] and x :: (y :: _ as rest) name more elements.
Which list functions raise when there is no answer, and what replaces them?

List.hd, List.nth, List.find and List.assoc raise; nth_opt, find_opt and assoc_opt return None, which suits answers that may normally be missing.
Since when do List.take and List.drop exist, and what does a negative count do?

Since OCaml 5.3, where a negative count raised Invalid_argument; from 5.4 it takes nothing and drops nothing.
Which pair does an association-list lookup return, and when is it the wrong tool?

The leftmost pair with that key, so a pair added at the front hides an older one. It suits small tables; Map or Hashtbl suit large ones.
What type suits a function such as last that has no answer for []?

'a list -> 'a option, so the caller handles the empty case where it knows what to do.

Key takeaways

A list is [] or a value joined to a list with ::; each :: builds one immutable cell, so a new list shares the tail it was built on.
l1 @ l2 copies every cell of l1 and shares l2, so a list built by appending one element at a time costs about n²/2 cells, while :: and one List.rev cost 2n.
A list function has a case for [] and one for x :: rest; patterns such as [x] and x :: (y :: _ as rest) name more elements, and a forgotten [] draws warning 8.
List.hd, List.nth, List.find and List.assoc raise when there is no answer; nth_opt, find_opt, assoc_opt and a match with a [] case return None instead, which suits answers that may normally be missing.
An association list finds the leftmost pair with a key, so a pair added at the front hides an older one; it suits small tables, and Map or Hashtbl suit large ones.

Terms in this lesson

association list: A list of (key, value) pairs used as a small lookup table; List.assoc returns the value of the leftmost pair whose key matches.
cons cell: One link of an OCaml list, built by x :: tail: it holds a value, the head, and the rest of the list, the tail. A cell never changes, so lists can share their tails.

References

The OCaml Manual: module List (Inria and the OCaml developers)
Lists (OCaml.org)
The OCaml Manual: The core language (lists) (Inria and the OCaml developers)
Memory Representation of Values (OCaml.org)
The OCaml Manual: Batch compilation (warnings) (Inria and the OCaml developers)
The OCaml Manual: module Map (Inria and the OCaml developers)
The OCaml Manual: module Hashtbl (Inria and the OCaml developers)
OCaml Changes (the List functions each release added) (The OCaml developers)

Report a problem with this lesson

In this module: Lists, higher-order functions and laziness

Lists and list patterns Free lesson, Pro answers: 10 minutes
Map, filter and fold Free lesson, Pro answers: 10 minutes
Folds over trees, options and other structures Free lesson, Pro answers: 10 minutes
Sequences, laziness and memoization Free lesson, Pro answers: 20 minutes

What you will learn

Before you start

What you will learn

Before you start

A list is a chain of cells, built from the front

Patterns follow the two shapes a list can have

Functions that may find nothing come in two forms

An association list is the simplest lookup table

Practise: lists, patterns and lookups

Interview questions

A report builder adds each row with rows := !rows @ [row]. With 2,000 rows it finishes at once; with 50,000 rows it runs for about half a minute and allocates billions of words. Explain the cost, and rewrite the loop so the time grows in step with the number of rows.

An upload handler reads a file into a list of lines and calls List.hd lines to get the header row. An empty file stops it with Failure "hd" in production. Fix this case, and say how you would find similar calls before they fail.

Key takeaways

References