Skip to content
Tutorials Center
My learning

Topics

Lesson 30 of 40 ยท Modules and Functors

Standard Library Containers: Map, Set, Hashtbl, Queue and Stack

A practical tour of the OCaml standard library containers. Immutable Map and Set, mutable Hashtbl, Queue, Stack, Buffer and Seq, with complexity notes and guidance on which to choose.

OCaml's standard library (called Stdlib, with its modules such as List, Map and Hashtbl) ships a small, solid set of containers. Knowing which one to pick, and whether it is immutable or mutable, is a large part of writing idiomatic OCaml. The immutable ones return a new structure on every change and share most of the old one; the mutable ones update in place.

OCaml is not available in the site's code runners, so ocaml blocks are read-only and outputs are shown only when certain. The Python stand-ins mimic the behaviour of persistent versus mutable containers.

Choosing a container

Need Module Mutable? Lookup
Sequence processed front to back List no O(n)
Fixed-size indexable sequence Array yes O(1)
Key to value, ordered keys Map.Make no O(log n)
Set of values, ordered Set.Make no O(log n)
Key to value, fast average lookup Hashtbl yes O(1) average
First in, first out Queue yes O(1) push/pop
Last in, first out Stack yes O(1) push/pop
Building a string Buffer yes O(1) append
Lazy sequence Seq no -

Map: immutable dictionary

OCAML
module SMap = Map.Make (String)

let scores =
  SMap.empty |> SMap.add "ada" 90 |> SMap.add "grace" 95 |> SMap.add "ada" 92

let () =
  print_int (SMap.find "ada" scores);          (* 92: add replaced the old binding *)
  print_newline ();
  print_int (SMap.cardinal scores)             (* 2 *)

Useful operations: find_opt, mem, remove, update, fold, iter, map, filter, bindings (sorted by key), min_binding_opt, to_seq. SMap.find raises Not_found if the key is absent, so prefer find_opt.

Maps are persistent: after let scores2 = SMap.add "linus" 70 scores, the old scores is still valid and unchanged. That makes backtracking, undo and sharing state between threads easy.

SMap.update is the neat way to modify a value by a function:

OCAML
let incr_count key m =
  SMap.update key (function None -> Some 1 | Some n -> Some (n + 1)) m

Set

OCAML
module IntSet = Set.Make (Int)

let a = IntSet.of_list [ 1; 2; 3; 4 ]
let b = IntSet.of_list [ 3; 4; 5 ]

let common = IntSet.inter a b          (* {3, 4} *)
let all = IntSet.union a b             (* {1, 2, 3, 4, 5} *)
let only_a = IntSet.diff a b           (* {1, 2} *)
let () = Printf.printf "%b\n" (IntSet.mem 3 a)   (* prints: true *)

IntSet.elements returns a sorted list. Sets and maps need an ordering module, which is why they come from functors.

Hashtbl: mutable hash table

OCAML
let counts : (string, int) Hashtbl.t = Hashtbl.create 16

let bump w =
  let n = Option.value (Hashtbl.find_opt counts w) ~default:0 in
  Hashtbl.replace counts w (n + 1)

let () =
  List.iter bump [ "a"; "b"; "a"; "c"; "a" ];
  Printf.printf "a=%d\n" (Hashtbl.find counts "a")
(* prints: a=3 *)

Details worth knowing:

  • Use Hashtbl.replace to overwrite. Hashtbl.add stacks a second binding on the same key, which shadows the first until it is removed, a classic surprise.
  • The initial size is a hint; the table grows automatically.
  • Hashtbl.hash is structural and works on most values. For custom keys or case-insensitive hashing use Hashtbl.Make.
  • Iteration order is unspecified.

Queue and Stack

OCAML
let q = Queue.create ()
let () =
  Queue.add 1 q; Queue.add 2 q; Queue.add 3 q;
  Printf.printf "%d\n" (Queue.take q)       (* prints: 1 *)

let s = Stack.create ()
let () =
  Stack.push 1 s; Stack.push 2 s;
  Printf.printf "%d\n" (Stack.pop s)        (* prints: 2 *)

Queue.take raises Queue.Empty when empty; Queue.take_opt and Stack.pop_opt return options. A queue is what breadth-first search needs (see the graph practice problems).

Buffer: efficient string building

Repeated ^ copies the string each time, which is quadratic. A Buffer appends in amortised constant time:

OCAML
let join_numbers n =
  let b = Buffer.create 64 in
  for i = 1 to n do
    if i > 1 then Buffer.add_char b ',';
    Buffer.add_string b (string_of_int i)
  done;
  Buffer.contents b

let () = print_endline (join_numbers 5)
(* prints: 1,2,3,4,5 *)

Seq: lazy sequences

Seq.t is a lazily evaluated sequence, handy for infinite or large data:

OCAML
let naturals = Seq.ints 0
let squares = Seq.map (fun x -> x * x) naturals
let first_five = squares |> Seq.take 5 |> List.of_seq
(* [0; 1; 4; 9; 16] *)

Nothing is computed until a consumer such as List.of_seq or Seq.iter pulls values.

Stand-in: persistent versus mutable

Python Stand-in: persistent map and mutable table

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

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Python Stand-in: queue-driven traversal

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

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Common mistakes

  • Using Hashtbl.add where replace was meant.
  • Using List.assoc or List.mem as a map for large data: it is O(n) per lookup.
  • Using ^ in a loop to build large strings.
  • Keeping a Map in a ref without need: the persistent version is often all you want, passed through a fold.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What happens to the old map after let m2 = SMap.add k v m1?

    Map is a persistent data structure, so updates return a new map and share structure with the old one.
  2. 2. Which call overwrites an existing key in a Hashtbl?

    add hides the previous binding but keeps it; replace overwrites.
  3. 3. Which structure suits breadth-first search?

    BFS visits nodes in first-in, first-out order.
  4. 4. Why prefer Buffer over repeated ^ in a loop?

    Buffer appends in amortised constant time and produces the string once at the end.

Summary

  • Map and Set are persistent and built with functors; Hashtbl, Queue, Stack and Buffer are mutable.
  • Prefer find_opt-style lookups and Hashtbl.replace.
  • Use Buffer for building strings and Seq for lazy pipelines.
  • Choose by access pattern: ordered, hashed, FIFO or LIFO.

Next: References and Mutable State