How can I define a recursive Base.Set type?

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).

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));;
1 Like

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));;
1 Like

This helps a lot. I happen to face the same problems (and I am new to Base).

May I ask how to use deriving sexp_of in this example? It seems I cannot simply put this after the definition of type t.

Edit:

I still don’t figure out how to add deriving sexp_of on this code. But I later found RWO gives an example on creating a new set without mentioning comparator_witness

type string_int_map =
  int Map.M(String).t
[@@deriving sexp]
;;
type string_int_map = int Base.Map.M(Base.String).t
val string_int_map_of_sexp : Sexp.t -> string_int_map = 
val sexp_of_string_int_map : string_int_map -> Sexp.t =

This idea works for my own code.