Skip to content
Tutorials Center
My learning

Topics

Lesson 20 of 40 ยท Lists, Arrays and Records

Sorting and Association Lists in OCaml

Sort lists with List.sort and custom comparison functions, sort by several keys, deduplicate, and use association lists as simple key-value tables with assoc and remove_assoc.

This lesson covers two everyday needs: putting list elements in order, and storing key-value pairs in a list. Both rely on small functions you pass to the List module.

Sorting with List.sort

OCAML
val List.sort : ('a -> 'a -> int) -> 'a list -> 'a list

List.sort takes a comparison function and a list. The comparison function returns a negative number if the first argument comes first, zero if they are equal, and a positive number if the second comes first. The standard compare does that for any type:

OCAML
# List.sort compare [5; 2; 9; 1];;
- : int list = [1; 2; 5; 9]
# List.sort compare ["pear"; "apple"; "fig"];;
- : string list = ["apple"; "fig"; "pear"]

The original list is unchanged (lists are immutable); you get a new sorted list. The sort is a stable merge sort running in O(n log n): equal elements keep their original relative order. List.stable_sort is identical, and List.fast_sort is the same algorithm too.

Descending order and custom comparisons

Swap the arguments:

OCAML
let descending a b = compare b a
# List.sort descending [5; 2; 9; 1];;
- : int list = [9; 5; 2; 1]

Compare by a key:

OCAML
let by_length a b = compare (String.length a) (String.length b)
# List.sort by_length ["banana"; "fig"; "apple"];;
- : string list = ["fig"; "apple"; "banana"]

A reusable helper that sorts by any key function:

OCAML
let compare_on key a b = compare (key a) (key b)

let sorted = List.sort (compare_on snd) [("a", 3); ("b", 1); ("c", 2)]
(* [("b", 1); ("c", 2); ("a", 3)] *)

Because the type int is returned, avoid writing a - b for comparing ints: subtraction can overflow. Use compare or Int.compare.

Typed comparison functions

compare is polymorphic and slightly slower than the type-specific Int.compare, String.compare and Float.compare. In a hot loop, prefer those:

OCAML
let sorted = List.sort Int.compare [3; 1; 2]

Sorting by several keys

Compare the first key, and fall back to the second only when equal. Tuples already compare this way:

OCAML
let people = [("Zoe", 25); ("Adam", 40); ("Adam", 30)]
let sorted = List.sort compare people
(* [("Adam", 30); ("Adam", 40); ("Zoe", 25)] *)

For different orders per key, chain with a helper:

OCAML
let then_by cmp1 cmp2 a b =
  let c = cmp1 a b in
  if c <> 0 then c else cmp2 a b

let age_desc_then_name =
  then_by (fun (_, a1) (_, a2) -> compare a2 a1)
          (fun (n1, _) (n2, _) -> compare n1 n2)

let r = List.sort age_desc_then_name people
(* [("Adam", 40); ("Adam", 30); ("Zoe", 25)] *)

Removing duplicates

OCAML
# List.sort_uniq compare [3; 1; 3; 2; 1];;
- : int list = [1; 2; 3]

sort_uniq sorts and drops elements that compare equal. If the order of first appearance matters instead, track what you have seen in a Hashtbl or set.

Minimum and maximum

The shortest way to find an extreme element is a fold:

OCAML
let max_by key = function
  | [] -> None
  | x :: rest ->
      Some (List.fold_left (fun best y -> if key y > key best then y else best) x rest)

Association lists

An association list is a list of pairs (key, value). It is the simplest dictionary in OCaml and is perfect for small tables.

OCAML
let ages = [("ada", 36); ("alan", 41); ("grace", 85)]

The functions are in List:

OCAML
# List.assoc "alan" ages;;
- : int = 41
# List.assoc_opt "bob" ages;;
- : int option = None
# List.mem_assoc "grace" ages;;
- : bool = true
# List.remove_assoc "ada" ages;;
- : (string * int) list = [("alan", 41); ("grace", 85)]

List.assoc raises Not_found if the key is missing, so use assoc_opt in most cases. Lookups scan the list from the front and compare with structural equality, taking O(n). Variants assq, mem_assq and remove_assq compare keys with physical equality == instead.

Updating

Association lists are immutable. To "update", put the new binding at the front; lookups find the first match, so it shadows the old one. Or remove and add:

OCAML
let set key value l = (key, value) :: List.remove_assoc key l
let ages2 = set "alan" 42 ages
(* [("alan", 42); ("ada", 36); ("grace", 85)] *)

When to use something else

An association list is fine up to a few dozen entries. For bigger tables use:

  • Hashtbl for fast mutable maps keyed by anything hashable,
  • Map.Make(...) for ordered immutable maps,
  • the Set module for collections without values.

Map and Hashtbl appear in later chapters.

Putting the two together: a leaderboard

OCAML
let scores = [("ada", 90); ("alan", 75); ("grace", 90); ("linus", 60)]

let ranked =
  List.sort
    (fun (n1, s1) (n2, s2) ->
      let c = compare s2 s1 in
      if c <> 0 then c else compare n1 n2)
    scores

let () =
  List.iteri (fun i (name, score) -> Printf.printf "%d. %s %d\n" (i + 1) name score) ranked

It prints 1. ada 90, 2. grace 90, 3. alan 75, 4. linus 60.

A stand-in: sort and lookup

JavaScript's sort takes the same kind of comparison function. The stand-in sorts by several keys and implements assoc_opt and set over an array of pairs.

JS Stand-in: custom comparison and assoc lists

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 must the comparison function given to List.sort return?

    Like compare, it returns a negative integer, zero or a positive integer.
  2. 2. How do you sort a list in descending order?

    Swapping the arguments of compare reverses the order.
  3. 3. What does List.assoc_opt "bob" ages return if "bob" is not a key?

    assoc_opt returns an option; assoc raises Not_found.
  4. 4. What is the lookup cost in an association list of n pairs?

    Lookup scans the list from the front.

Summary

  • List.sort cmp l returns a new sorted list; cmp returns a negative, zero or positive int.
  • Reverse the arguments for descending order; build comparison helpers for keys and multiple keys.
  • List.sort_uniq sorts and removes duplicates.
  • Association lists store (key, value) pairs with assoc_opt, mem_assoc and remove_assoc.
  • Use Hashtbl or Map for larger tables.

Next: Arrays