Standard Data Structures

Custom hashing via the functor Hashtbl.Make (struct type t = ...

18.1 Hashtbl — mutable hash table

Custom hashing via the functor Hashtbl.Make (struct type t = ... let equal = ... let hash = ... end).

let h : (string, int) Hashtbl.t = Hashtbl.create 16
let () =
  Hashtbl.replace h "apple" 3;     (* add or overwrite *)
  Hashtbl.add h "pear" 5           (* add shadows; prefer replace *)

Hashtbl.find h "apple"            (* 3 or Not_found *)
Hashtbl.find_opt h "kiwi"         (* None *)
Hashtbl.mem h "pear"
Hashtbl.remove h "pear"
Hashtbl.length h
Hashtbl.iter (fun k v -> Printf.printf "%s=%d\n" k v) h
Hashtbl.fold (fun k v acc -> (k, v) :: acc) h []
Hashtbl.to_seq_keys h |> List.of_seq
Hashtbl.reset h

(* Word count *)
let word_count words =
  let tbl = Hashtbl.create 64 in
  List.iter (fun w ->
    let n = Option.value ~default:0 (Hashtbl.find_opt tbl w) in
    Hashtbl.replace tbl w (n + 1)) words;
  tbl

18.2 Map — immutable balanced-tree map (functor)

Keys need a module with type t and compare : t -> t -> int:

module StringMap = Map.Make (String)

let m =
  StringMap.empty
  |> StringMap.add "one" 1
  |> StringMap.add "two" 2

StringMap.find "one" m             (* 1 *)
StringMap.find_opt "three" m       (* None *)
StringMap.mem "two" m
StringMap.remove "one" m
StringMap.update "one" (function None -> Some 1 | Some n -> Some (n + 1)) m
StringMap.iter (fun k v -> Printf.printf "%s->%d\n" k v) m
StringMap.fold (fun k v acc -> acc + v) m 0
StringMap.bindings m               (* sorted (key, value) list *)
StringMap.cardinal m
StringMap.map, StringMap.filter, StringMap.union, StringMap.merge
StringMap.of_seq (List.to_seq [("a",1)])

module IntPairMap = Map.Make (struct
  type t = int * int
  let compare = compare
end)

18.3 Set

module IntSet = Set.Make (Int)
let s = IntSet.of_list [3; 1; 4; 1; 5]
IntSet.elements s                  (* [1;3;4;5] *)
IntSet.mem 4 s
IntSet.add, IntSet.remove, IntSet.union, IntSet.inter, IntSet.diff
IntSet.subset, IntSet.cardinal, IntSet.min_elt, IntSet.max_elt

18.4 Stack and Queue (mutable)

let s = Stack.create ()
let () = Stack.push 1 s; Stack.push 2 s
Stack.pop s, Stack.top s, Stack.is_empty s, Stack.pop_opt s

let q = Queue.create ()
let () = Queue.add 1 q; Queue.push 2 q
Queue.take q, Queue.peek q, Queue.length q, Queue.take_opt q

18.5 Purely functional queue (two lists)

type 'a fqueue = { front : 'a list; back : 'a list }
let empty = { front = []; back = [] }
let push x q = { q with back = x :: q.back }
let pop q = match q.front with
  | x :: f -> Some (x, { q with front = f })
  | [] -> match List.rev q.back with
    | [] -> None
    | x :: f -> Some (x, { front = f; back = [] })

18.6 Seq — lazy sequences

Every collection has to_seq/of_seq — Seq is the universal glue for conversions.

(* Definition in the stdlib:
   type 'a t = unit -> 'a node
   and 'a node = Nil | Cons of 'a * 'a t *)

let rec naturals n () = Seq.Cons (n, naturals (n + 1))

naturals 0
|> Seq.filter (fun x -> x mod 3 = 0)
|> Seq.map (fun x -> x * x)
|> Seq.take 5
|> List.of_seq               (* [0;9;36;81;144] *)

Seq.ints 0, Seq.repeat, Seq.iterate succ 0, Seq.unfold, Seq.zip, Seq.fold_left

18.7 Other stdlib modules worth knowing

Random, Int, Float, Bool, Uchar, Lazy, Weak, Ephemeron, Gc, Sys, Filename, Printexc, Obj (unsafe — avoid), Atomic, Domain, Mutex, Condition, Semaphore, Effect, In_channel, Out_channel, Type (5.1+), Either.

Random.self_init ();
Random.int 100, Random.float 1.0, Random.bool ()
let st = Random.State.make [|42|] in Random.State.int st 10   (* reproducible *)