Where can I see how OCaml’s standard library functions are implemented?

Question

I'm interested in how List.init and other library functions are implemented in OCaml. Where can I see the implementations? I checked this official link: https://v2.ocaml.org/api/List.html and only found the function signatures.

Answer 1

OCaml, including its standard library, is entirely open source and at time of writing hosted on GitHub here: https://github.com/ocaml/ocaml/

The List.init function (located here) is split across a couple utility functions and actually has two different implementations with different performance characteristics that is selected based on a stack size heuristic and the length of the requested list:

let rec init_tailrec_aux acc i n f =
  if i >= n then acc
  else init_tailrec_aux (f i :: acc) (i+1) n f

let rec init_aux i n f =
  if i >= n then []
  else
    let r = f i in
    r :: init_aux (i+1) n f

let rev_init_threshold =
  match Sys.backend_type with
  | Sys.Native | Sys.Bytecode -> 10_000
  (* We don't know the size of the stack, better be safe and assume it's
     small. *)
  | Sys.Other _ -> 50

let init len f =
  if len < 0 then invalid_arg "List.init" else
  if len > rev_init_threshold then rev (init_tailrec_aux [] 0 len f)
  else init_aux 0 len f

Answer 2

You can always read the implementation in the sources: https://github.com/ocaml/ocaml/blob/trunk/stdlib/list.ml

Answer 3

If you have an OCaml source release, you can find the standard library implementation in the stdlib directory. The list implementation is stdlib/list.ml.

Here is List.init:

let rec init_tailrec_aux acc i n f =
  if i >= n then acc
  else init_tailrec_aux (f i :: acc) (i+1) n f

let rec init_aux i n f =
  if i >= n then []
  else
    let r = f i in
    r :: init_aux (i+1) n f

let rev_init_threshold =
  match Sys.backend_type with
  | Sys.Native | Sys.Bytecode -> 10_000
  (* We don't know the size of the stack, better be safe and assume it's
     small. *)
  | Sys.Other _ -> 50

let init len f =
  if len < 0 then invalid_arg "List.init" else
  if len > rev_init_threshold then rev (init_tailrec_aux [] 0 len f)
  else init_aux 0 len f

You can find recent OCaml releases on github. Here is a link to the latest release at the present time (I believe): OCaml 4.14.0 source tgz