list.ml

include Stdlib.List

let scan f ?init xs =
  let scan' xs = 
    let rec aux acc xs =
      match acc, xs with
      | _, [] -> acc
      | [], x :: xs -> aux [x] xs
      | x :: _, y :: ys -> aux (f x y :: acc) ys
    in
    aux [] xs |> rev
  in
  match init, xs with
  | None, [] -> []
  | None, xs -> scan' xs
  | Some x, xs -> scan' @@ x :: xs
  
let collect f xs =
  let rec aux f acc = function
    | [] -> acc
    | x :: xs -> aux f (f x acc) xs
  in
  aux (fun x xs -> aux cons xs @@ f x) [] xs |> rev

let reduce_left f = function
  | [] -> failwith "`xs` must has value"
  | x :: xs ->
    let rec aux acc = function
      | [] -> acc
      | x :: xs -> aux (f acc x) xs 
    in
    aux x xs

let reduce_right f = function
  | [] -> failwith "`xs` must has value"
  | xs ->
    let aux f arr start fin acc =
      let state = ref acc in
      for i = fin downto start do
        state := f (Array.get arr i) !state
      done;
      !state
    in
    let arr = Array.of_list xs in
    let len = Array.length arr in
    aux f arr 0 (len - 2) (Array.get arr @@ len - 1)

list.mli

include module type of Stdlib.List

val scan : ('a -> 'a -> 'a) -> ?init:'a -> 'a t -> 'a t
val collect : ('a -> 'b t) -> 'a t -> 'b t
val reduce_left : ('a -> 'a -> 'a) -> 'a t -> 'a
val reduce_right : ('a -> 'a -> 'a) -> 'a t -> 'a

let () =
  let xs = [1; 2; 3; 4] in
  let print_intlist xs =
    Printf.printf "[%s]\n" @@ String.concat "; " @@ List.map string_of_int xs
  in

  print_intlist @@ List.scan (+) lst; (* [1; 3; 6; 10] *)
  print_intlist @@ List.scan (+) ~init:0 lst; (* [0; 1; 3; 6; 10] *)
  print_intlist @@ List.scan ( * ) lst; (* [1; 2; 6; 24] *)
  print_intlist @@ List.scan ( * ) ~init:1 lst; (* [1; 1; 2; 6; 24] *)