prevent excessive sorting w/ phantom types

phantomTypeSample.ml

module MyArray : sig
  type ('a, 'status) t
  type regular
  type sorted
    
  val create : 'a array -> ('a, regular) t
  val to_array : ('a, 'status) t -> 'a array
  val sort : ?comparer:('a -> 'a -> int) -> ('a, regular) t -> ('a, sorted) t
end = struct
  type ('a, 'status) t = Array of 'a array
  type regular
  type sorted
  
  let create xs = Array xs
  let to_array (Array xs) = xs
  let sort ?(comparer=compare) (Array array) =
    let new_array = Array.copy array in
    Array.sort comparer new_array;
    Array new_array
end

let string_of_array ~(to_string : 'a -> string) xs =
  let xs' = Array.to_list xs in
  "[|" ^ String.concat "; " (List.map to_string xs') ^ "|]"

let () =
  let xs = MyArray.create [|1; 3; 7; 2|] in
  let ys = MyArray.sort xs |> MyArray.to_array in
  print_endline (string_of_array ~to_string:string_of_int ys)
  (* [|1; 2; 3; 7|] *)

let () =
  let xs = MyArray.create [|1; 3; 7; 2|] in
  let ys = MyArray.sort xs in
  (* type error occured: MyArray.sort require "('a, regular) t" but present "('a, sorted) t" *)
  let zs = MyArray.sort ys |> MyArray.to_array in
  print_endline (string_of_array ~to_string:string_of_int zs)