核心的 `List.init` 在 Pervasives 中？

Question

我习惯了 JaneStreet 的 Core 图书馆。它的 List 模块有一个简洁的 init 函数：

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

它允许您使用自定义函数来创建一个列表来初始化元素：

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"]

不过Pervasives好像没有这个功能，很遗憾。我错过了什么，还是我必须自己实施？如果我确实需要编写它，我该如何实现？

编辑:

我写了 init 的命令式版本，但在这种情况下不得不求助于 OCaml 的命令式功能感觉不对。 :(

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
;;

编辑 2：

我在 OCaml 的 GitHub 上打开了一个 pull request 以包含此功能。

编辑 3：

该功能已在 OCaml 4.06 中发布。

Answer 1

递归实现相当简单。但是，它不是 tail-recursive，这意味着您将面临大型列表的堆栈溢出风险：

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

我们可以使用常用技术将其转换为 tail-recursive 版本：

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)

这使用累加器并且还需要反转中间结果，因为列表是反向构造的。请注意，我们也可以使用 f (n-i-1) 而不是 f i 来避免颠倒列表，但是如果 f 具有 side-effects.

，这可能会导致意外行为

另一种更短的解决方案是简单地使用 Array.init 作为起点：

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

Answer 2

您可以从 JaneStreet 复制代码并使用它。

代码看起来像（但不完全一样）：

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 []
;;

您可以从包 core_kernel.

中找到 core_list0.ml 中的原始代码

核心的 `List.init` 在 Pervasives 中？

Core's `List.init` in Pervasives?

ocaml

ocaml-core