Some fairly awful code for building up lists

list_build.ml

(* Third order function for imperatively building sequences in safe way,
 * even if the underlying implementation uses unsafety.
 *
 * Type is:
 *   build : (('a -> unit) -> 'b) -> 'a list * 'b
 *
 * "build f" calls "f push", where push is a function that adds its argument
 * to the sequence being built under the hood.
 *
 * Inliner needs to be pretty good for this to own.
 * (llvm's was when I tried this in Rust.)
 *)

(* Implement this legitimately by building the list backwards and then
 * reversing it. *)
let build_legit body =
  let l = ref [] in
  let push x = l := x :: !l in
  let x = body push in
  (List.rev !l, x)

type 'a bs_list = {
  head: 'a;
  mutable tail: 'a bs_list;
}

(* Using this forces the right type. *)
let bs_list_to_list : 'a bs_list -> 'a list = Obj.magic

(* Do the build by imperatively updating the list as we go. *)
let build_inplace body  =
  let rec dummy = { head = Obj.magic (); tail = dummy } in
  let last = ref dummy in
  let push x =
    let rec node = { head = x; tail = node } in
    (!last).tail <- node;
    last := node
  in
  let x = body push in
  (!last).tail <- Obj.magic []; (* Terminate the list *)
  (bs_list_to_list dummy.tail, x)


let build = build_inplace
let build' body = fst (build body)

let map f l =
  let body push =
    let rec loop = function
      | [] -> ()
      | x::xs -> push (f x); loop xs in
    loop l
  in build' body