Skip to content
Tutorials Center
My learning

Topics

Lesson 18 of 40 ยท Lists, Arrays and Records

The OCaml List Module

A practical tour of the Stdlib List module: length, nth, rev, map, filter, find, exists, for_all, partition, concat, init, iter and sort, with types, examples and pitfalls.

You rarely write recursion by hand for common list jobs, because the standard library's List module already contains the building blocks. Knowing the names and types of about twenty functions makes everyday code short. In this lesson we group them by purpose. You can explore the full list yourself in utop with #show List;;.

Inspecting a list

OCAML
# List.length [10; 20; 30];;
- : int = 3
# List.hd [10; 20; 30];;
- : int = 10
# List.tl [10; 20; 30];;
- : int list = [20; 30]
# List.nth [10; 20; 30] 2;;
- : int = 30
# List.is_empty [];;
- : bool = true

List.hd, List.tl and List.nth raise exceptions on lists that are too short (Failure "hd", Invalid_argument "List.nth"). Pattern matching is usually safer. The _opt variants return None instead, such as List.nth_opt. (List.is_empty needs OCaml 5.1 or later.)

Building lists

OCAML
# List.init 4 (fun i -> i * 10);;
- : int list = [0; 10; 20; 30]
# List.rev [1; 2; 3];;
- : int list = [3; 2; 1]
# List.concat [[1; 2]; [3]; []; [4; 5]];;
- : int list = [1; 2; 3; 4; 5]
# List.append [1] [2; 3];;
- : int list = [1; 2; 3]
# List.flatten [["a"]; ["b"; "c"]];;
- : string list = ["a"; "b"; "c"]

Transforming

OCAML
# List.map (fun x -> x * x) [1; 2; 3];;
- : int list = [1; 4; 9]
# List.mapi (fun i x -> (i, x)) ["a"; "b"];;
- : (int * string) list = [(0, "a"); (1, "b")]
# List.concat_map (fun x -> [x; x]) [1; 2];;
- : int list = [1; 1; 2; 2]
# List.filter_map (fun s -> int_of_string_opt s) ["1"; "x"; "3"];;
- : int list = [1; 3]
  • mapi also passes the index.
  • concat_map maps to lists and joins them.
  • filter_map maps to options and keeps the Some values. It is a very handy way to parse and drop errors at once.

Filtering and splitting

OCAML
# List.filter (fun n -> n mod 2 = 0) [1; 2; 3; 4];;
- : int list = [2; 4]
# List.partition (fun n -> n < 3) [1; 2; 3; 4];;
- : int list * int list = ([1; 2], [3; 4])
# List.find_all (fun n -> n > 1) [1; 2; 3];;
- : int list = [2; 3]

List.partition returns a pair: the elements that satisfy the test and those that do not. find_all is a synonym of filter.

Searching

OCAML
# List.mem 3 [1; 2; 3];;
- : bool = true
# List.exists (fun x -> x > 2) [1; 2; 3];;
- : bool = true
# List.for_all (fun x -> x > 0) [1; 2; 3];;
- : bool = true
# List.find_opt (fun x -> x > 1) [1; 2; 3];;
- : int option = Some 2
# List.find (fun x -> x > 5) [1; 2; 3];;
Exception: Not_found.

Prefer find_opt to find: it returns None rather than raising. List.assoc works with association lists; see Sorting and association lists.

Other searches: List.find_index and List.find_mapi (5.1), List.mem_assoc, List.exists2.

Iterating for effects

OCAML
let () = List.iter print_endline ["one"; "two"; "three"]
let () = List.iteri (fun i s -> Printf.printf "%d: %s\n" i s) ["a"; "b"]

List.iter takes a function returning unit. The output of the second is 0: a and 1: b.

Working with two lists

OCAML
# List.combine [1; 2; 3] ["a"; "b"; "c"];;
- : (int * string) list = [(1, "a"); (2, "b"); (3, "c")]
# List.split [(1, "a"); (2, "b")];;
- : int list * string list = ([1; 2], ["a"; "b"])
# List.map2 (+) [1; 2; 3] [10; 20; 30];;
- : int list = [11; 22; 33]

combine and map2 raise Invalid_argument if the lists have different lengths. In OCaml 5.1, List.equal and List.compare compare lists with a custom element function.

Sorting and deduplicating

OCAML
# List.sort compare [3; 1; 2];;
- : int list = [1; 2; 3]
# List.sort (fun a b -> compare b a) [3; 1; 2];;
- : int list = [3; 2; 1]
# List.sort_uniq compare [3; 1; 3; 2; 1];;
- : int list = [1; 2; 3]

List.sort is stable-merge (List.stable_sort is the same). We talk more about ordering in a later lesson.

Taking and dropping (OCaml 5.3)

Recent versions added List.take and List.drop:

OCAML
# List.take 2 [1; 2; 3; 4];;
- : int list = [1; 2]
# List.drop 2 [1; 2; 3; 4];;
- : int list = [3; 4]

If your compiler is older, write them with recursion.

Choosing the right function

I want to... Use
change every element map
keep some elements filter
change and keep some filter_map
answer yes/no about the list exists, for_all, mem
get the first match find_opt
split in two by a test partition
reduce to one value fold_left (next lesson)
run an effect iter

A stand-in: the same operations on arrays

JavaScript's array methods line up closely with the List functions. The stand-in is a cheat sheet in code form.

JS Stand-in: List functions as array methods

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. Which function keeps the Some results of mapping a function that returns options?

    filter_map applies f, drops None and unwraps Some.
  2. 2. What is safer than List.find when no match is possible?

    find_opt returns an option; find raises Not_found.
  3. 3. What does List.partition (fun n -> n < 3) [1; 2; 3; 4] return?

    It returns the pair (elements satisfying the test, elements that do not).
  4. 4. What does List.map2 (+) [1; 2] [10; 20; 30] do?

    map2 requires lists of equal length.

Summary

  • List offers inspecting, building, transforming, filtering, searching, iterating and sorting functions.
  • Prefer the _opt variants and pattern matching over functions that raise.
  • filter_map, concat_map and partition replace many hand-written loops.
  • sort, sort_uniq and compare order and deduplicate.
  • take and drop exist in new compilers; older ones need your own version.

Next: Folds on lists