Ядро «List.init» в Pervasives?

Question

Я привык к библиотеке Core JaneStreet. Его 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, что печально. Я что-то упускаю, или я должен сам его реализовать? И если мне нужно это написать, как мне это достичь?

EDIT:

Я написал императивную версию 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 
;; 

EDIT 2:

Я открыл pull request на GitHub OCaml, чтобы иметь эту функцию включены

Answer 1

Рекурсивная реализация довольно проста, однако, это не хвост.. -рекурсивный, что означает, что вы рискуете переполнением стека для больших списков:

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 

Мы можем превратить его в хвостовой рекурсии версию с использованием обычных методов:

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 имеет побочные эффекты.

Альтернативные и короче решения просто использовать 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_list0.ml из пакета core_kernel.