sortedlist.ml

(* Functor SortedList.Make resembling Map.Make and Set.Make
   it is an artificial data structure similar to the normal list, but keeps elements sorted 
 *)

module type ORD = sig
  type t
  val compare : t -> t -> int
end

module SortedList = struct
  module Make(Ord:ORD) = struct
    type t = Ord.t list
    
    let make () = []

    let rec put x ls =
      match ls with
      | hd :: tl when compare x hd < 0 -> hd :: put x tl 
      | _ -> x::ls

    let take ls = 
      match ls with
      | hd :: tl -> Some (hd,tl)
      | _ -> None

    let iter f ls = List.iter f ls
  end
end

module Test = struct
  module Int = struct type t = int let compare = compare (* using the built-in function *) end
  module SL = SortedList.Make(Int)

  let run () =
    (* create a sorted list, populate with integers *)
    let sorted_ls =
      List.fold_left 
        ( fun sls x -> SL.put x sls ) 
        ( SL.make() )
        [6;5;1;5;3;2;10;8]
    in
    (* print it out *)
    SL.iter (fun x -> Printf.printf "%i " x) sorted_ls;
    Printf.printf "\n"
  
end

let _ =
  Test.run()