Core's `List.init` in Pervasives?

问题:

I'm used to JaneStreet's Core library. Its List module has a neat init function:

List.init;;
- : int -> f:(int -> 'a) -> 'a list = <fun>

It allows you to create a list with using a custom function to initialize elements:

List.init 5 ~f:(Fn.id);;
- : int list = [0; 1; 2; 3; 4]

List.init 5 ~f:(Int.to_string);;
- : string list = ["0"; "1"; "2"; "3"; "4"]

However, this function doesn't seem to exist in Pervasives, which is sad. Am I missing something, or do I have to implement it myself? And if I do need to write it, how do I achieve this?

EDIT:

I have written an imperative version of init, but it doesn't feel right to have to resort to OCaml's imperative features in such a case. :(

let init n ~f =
  let i = ref 0 in
  let l = ref [] in
  while !i < n do
    l := (f !i) :: !l;
    incr i;
  done;
  List.rev !l
;;

EDIT 2:

I've opened a pull request on OCaml's GitHub to have this feature included.

EDIT 3:

The feature was released in OCaml 4.06.

回答1:

A recursive implementation is fairly straightforward. However, it is not tail-recursive, which means that you'll risk a stack overflow for large lists:

let init_list n ~f =
  let rec init_list' i n f =
    if i >= n then []
    else (f i) :: (init_list' (i+1) n f)
  in init_list' 0 n f

We can transform it into a tail-recursive version using the usual techniques:

let init_list n ~f =
  let rec init_list' acc i n f =
    if i >= n then acc
    else init_list' ((f i) :: acc) (i+1) n f
  in List.rev (init_list' [] 0 n f)

This uses an accumulator and also needs to reverse the intermediate result, as the list is constructed in reverse. Note that we could also use f (n-i-1) instead of f i to avoid reversing the list, but this may lead to unexpected behavior if f has side-effects.

An alternative and shorter solution is to simply use Array.init as a starting point:

let init_list n ~f = Array.(init n f |> to_list)

回答2:

You can copy the code from JaneStreet and use it.

The code look's like (but not exactly the same) :

let init n ~f =
  if n < 0 then raise (Invalid_argument "init");
  let rec loop i accum =
    if i = 0 then accum
    else loop (i-1) (f (i-1) :: accum)
  in
  loop n []
;;

You can find the original code inside core_list0.ml from the package core_kernel.