How can I define a recursive Base.Set type?


#1

I’m kind of stuck trying to figure out how can I use Base.Set in a recursive type definition.

So what I basically want ot achieve is something like this:
type value =
| Integer of int
| Float of float
| String of string
| Boolean of bool
| Variable of string
| Set of value Base.Set.t

But Base.Set constructor needs and element type and a comparator type ( type ('elt, 'cmp) t ). Element type is a no brainer, but I have no idea how I can define a comparator type. Not to mention I would need a comparator which can work on this recursive type.

I found an answer for making it work with Stdlib.Set by using recursive modules, but Base.Set doesn’t really have a similiar working functor like Stdlib.Set does(Make).


#2

You can use recursive module too, but this time with the comparator module. For instance,

module T: sig
  type t = Set of (t, Cmp.comparator_witness) Set.t
end = T
and Cmp : Comparator.S with type t = T.t =
struct
  type t = T.t
  include Comparator.Make(struct
    let compare x y = ...
     let sexp_of_t x = ...
   end)
end
let empty = T.Set (Set.empty (module Cmp));;

#3

Thanks a lot. Helped me to get this compileable example:

module rec MyType: sig
  type t = Set of (t, MyComparator.comparator_witness) Base.Set.t
  val compare: t -> t -> int
  val sexp_of_t: t -> Base.Sexp.t
end = struct 
  type t = Set of (t, MyComparator.comparator_witness) Base.Set.t
  let compare x y = -1
  let sexp_of_t x = Base.Sexp.Atom "1"
end
and MyComparator : Base.Comparator.S with type t = MyType.t =
struct
  type t = MyType.t
  include Base.Comparator.Make(MyType)
end
let empty = MyType.Set (Base.Set.empty (module MyComparator));;