merge_fold_left.ml

let merge_fold_left' ~compare fx fy fxy xs ys ini =
  let rec loop acc = function
    | x :: xs, y :: ys ->
       let c = compare x y in
       if      c < 0 then loop (fx x acc)    (xs,      y :: ys)
       else if c > 0 then loop (fy y acc)    (x :: xs, ys)
       else               loop (fxy x y acc) (xs,      ys)
    | x :: xs, []      -> loop (fx x acc)    (xs,      [])
    | [],      y :: ys -> loop (fy y acc)    ([],      ys)
    | [],      [] ->      acc
  in
  loop ini (xs, ys)
  
let[@ocaml.inline] merge_fold_left ~compare f xs ys ini =
  merge_fold_left' ~compare
    (fun x   z -> f (Some x) None     z)
    (fun   y z -> f None     (Some y) z)
    (fun x y z -> f (Some x) (Some y) z)
    xs ys ini

let[@ocaml.inline] rev_merge ~compare xs ys =
  merge_fold_left' ~compare
    (fun x   zs -> x      :: zs)
    (fun   y zs ->      y :: zs)
    (fun x y zs -> x :: y :: zs)
    xs ys []

let[@ocaml.inline] merge ~compare xs ys =
  rev_merge ~compare xs ys |> List.rev