Source

ocaml-toys / misc / sortedList.ml

Full commit
module type OrderedType = sig
  type t
  val cost: t -> int
end

module Make = functor(Elt: OrderedType) ->
  struct
    type t = {value:Elt.t; cost:int}
    
    let empty = []
    
    let is_empty lst = lst = []
                    
    let rec insert lst value = 
      let cost = Elt.cost value in
      match lst with
      | [] -> {value=value; cost=cost} :: lst
      | h::q ->         
        if cost < h.cost then {value=value; cost=cost} :: lst else h :: (insert q value)

    let singleton value = insert empty value

    let select lst = (List.hd lst).value

    let tl lst = List.tl lst    
  end