(* Set implemented *without* ad-hoc-polymorphic equality "=" (the
   "dirty" one): *)
module type SetSignature = sig
  type 'a set;;
  type 'a equality = 'a -> 'a -> bool;;
  val add : ('a equality) -> 'a -> ('a set) -> ('a set);;
  val belongs : ('a equality) ->'a -> ('a set) -> bool;;
  val empty : 'a set;;
end;;

module Set : SetSignature = struct
  type 'a set = 'a list;;
  type 'a equality = 'a -> 'a -> bool;;
  let empty = [];;
  let rec belongs equality x set =
    match set with
      | [] -> false
      | first :: rest ->
        if equality first x then
          true
        else
          belongs equality x rest;;
  let rec add equality x set =
    match set with
      | [] -> [x]
      | first :: rest ->
        if equality first x then
          set
        else
          first :: (add equality x rest);;
end;;