Ocaml modules implementation

Question

As everybody knows, Ocaml lets to use various modules: List, Map, Nativeint, etc. I know, that interfaces for these modules are provided (e.g. for List module: http://caml.inria.fr/pub/docs/manual-ocaml/libref/List.html), but I am interested in algorithms (= implementation = code) used in modules' functions. So - where can I find that?

Thanks for help.

Answer 1

You can find the definitions in the OCaml source code. For example, implementation of the Map functions is in stdlib/map.ml in the OCaml source distribution.

Answer 2

They should already be installed on your system. Most likely (assuming a Unix system) they are located in /usr/lib/ocaml or /usr/local/lib/ocaml. Just open any of the .ml files.

Answer 3

• On your system: /usr/lib/ocaml/list.ml and other.ml files
• On the web: http://docs.camlcity.org/docs/godilib/3.11/stdlib for a web-based version. Click on "List" then list.ml to see the List module implementation (.mli files being the interface).

---

The list implementations are interesting to look and understand. 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:

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

The first one prints 321, and the second one 123. The official map implementation forces the evaluation of f a, which could produce side effects! We want those to be produced in the correct order.

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