Ocaml modules implementation

Question

Ocaml's standard library contains various modules: List, Map, Nativeint, etc. I know that interfaces for these modules are provided (e.g. for the List module), but I am interested in the algorithms and their implementations used in modules' functions.

Where can I find that?

Answer 1

• On your system: /usr/lib/ocaml/list.ml and other .ml files
• On the web: https://github.com/ocaml/ocaml/blob/trunk/stdlib/list.ml and other .ml files in https://github.com/ocaml/ocaml/tree/trunk/stdlib

---

The List implementation is interesting to study. For example, the map function could be implemented like this:

let rec map f = function
  | [] -> []
  | a::l -> f a :: map f l

but is instead implemented like this:

let rec map f = function
  | [] -> []
  | a::l -> let r = f a in r :: map f l

What's the difference? Execute this:

List.map print_int [1;2;3] ;;
map print_int [1;2;3] ;;

The first one prints 123, but the second one prints 321! Since the evaluation of f a could produce side effects, it's important to force the correct order. This is what the official map implementation does. Indeed, the evaluation order of arguments is unspecified in OCaml even if all implementations follow the same order.

See also the Optimizing List.map post on the Jane Street blog for considerations on performance (List.map is efficient on small lists).