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.
Add a comment
|
3 Answers
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
3 Comments
Bergi
Now I'm curious: why is
init_aux preferable over init_tailrec_aux (if there's enough stack space for it)?
glennsl
It should be faster since it allocates half as much. The tail recursive implementation also has to reverse the list after it's constructed. See also this discussion on the performance of various implementations of
List.map: discuss.ocaml.org/t/…Bergi
Oh now I feel dumb, I didn't spot the
rev call which of course is necessary… I'm accustomed to putting the rev in the base case of the tail recursion where it would've been clearer.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
Comments
You can always read the implementation in the sources: https://github.com/ocaml/ocaml/blob/trunk/stdlib/list.ml
1 Comment
Chris
Links can break. Answers that link to source like this might be improved by including manageable chunks of code directly in the answer.