Core.Map in recursive type

Learning
1

I’m trying to use a Core.Map inside a recursive ADT as follows:

module T = struct
  type t = 
    | TInt of Int.t
    | TString of String.t
    | TMap of (t, t, _) Map.t

  let sexp_of_t = ...
  let compare = ...
end

include T
include Comparator.Make(T)

I’m not sure what to provide for the comparator_witness which is the third type argument for Map.t. I am used to getting the comparator_witness from Comparator.Make(T). Is there a standard way to do this?

A separate but related question: is @@deriving able to derive compare for ADTs involving Core.Map? I suspect not, but I haven’t tried due to the issue above.

2

Unfortunately, I haven’t worked out how to make [@@deriving compare] work with Core.Map because Map.compare is not defined (there is Map.compare_direct which I haven’t really figured out what it’s for). I had similar problems with [@@deriving sexp].

That being said, I think I worked out how to make a terrible hack compile, using recursive modules (the horror!):

open! Core

module T : sig
  type t [@@deriving sexp_of]

  include Comparable.S_plain with type t := t
end = struct
  module rec T1 : sig
    type t =
      | TInt of Int.t
      | TString of String.t
      | TMap of (t, t, T1.comparator_witness) Map.t
    [@@deriving sexp_of]

    include Comparator.S with type t := t
  end = struct
    module T0 = struct
      type t =
        | TInt of Int.t
        | TString of String.t
        | TMap of (t, t, T1.comparator_witness) Map.t

      let rec compare a b =
        match a, b with
        | TInt    x, TInt    y -> Int.compare x y
        | TInt    _, _         -> -1
        | TString x, TString y -> String.compare x y
        | TString _, TInt    _ -> 1
        | TString _, TMap    _ -> -1
        | TMap    x, TMap    y -> Map.compare_direct compare x y
        | TMap    _, _         -> 1
      ;;

      let sexp_of_t = sexp_of_opaque
    end
    include T0
    include Comparator.Make(T0)
  end
  include T1
  include Comparable.Make_plain_using_comparator(T1)
end

Basically, the hack is needed because the type definition for t requires the comparator_witness generated by Comparator.Make, before that functor has been applied. At least, I didn’t find a way around this but maybe somebody else could chime in?

1 Like
3

Wow! Thanks for going through the trouble.

I also came up with a (very scary) solution using recursive modules. I was hoping there was some trick I was missing.

As for @@deriving, I think compare_direct is precisely what you would want for a default total order over Core.Maps, but the trouble is you need a total order (compare) over the values in the map.

I have no experience writing ppx stuff so I don’t know what’s involved, but if the issue is just that you need to grab a sensible total order for Core.Map then I think compare_direct is what you want.

4

You may want to take a look at Base.Map instead. You should be able to derive things like so;

type t = Map.M(Int).t [@@deriving sexp, compare]
5

Ah, interesting. Reading the docs for Map.M it seems like the @@deriving ppx for compare tries to grab a total order for all the type arguments, and the issue is that comparator_witness obviously wont have one.

I guess for maps with equal keys, the derived compare breaks the tie with polymorphic compare over values?

Anyway, thanks for the pointer! I will use this from now on.