How to use Core.Tuple2 as a Core.Map key

Learning
1

Using Core, I’m trying to make a map keyed by tuples of integers. I understand how to do something like Map.empty (module String), but I don’t understand what’s going on fundamentally well enough to know how to make this work for something like Map.empty (module Tuple2); I assume that I need to somehow parameterize Tuple2 with the types of its members, but I can’t figure out the syntax to do it.

I worked around it by making my own module, but that feels suboptimal

module Foo = struct
  module IntTuple = struct
    type t = int * int
    let compare (x0, y0) (x1, y1) =
      match Pervasives.compare x0 x1 with
        0 -> Pervasives.compare y0 y1
      | c -> c

    let t_of_sexp tuple = Tuple2.t_of_sexp Int.t_of_sexp Int.t_of_sexp tuple
    let sexp_of_t tuple = Tuple2.sexp_of_t Int.sexp_of_t Int.sexp_of_t tuple
  end
  include IntTuple
  include Comparable.Make(IntTuple)
end

Given the above

let a = Map.empty (module Foo);; (* works as expected *)

let b = Map.empty (module (int, int) Tuple2);; (* doesn't compile *),
2

The line include Comparable.Make(IntTuple) injects several data structures specialized on Foo.IntTuple into module Foo. One of them happens to be an ordered map. You’re supposed to just use that module as it doesn’t require working with first class ones.

For example, you can add an element to the map and get it back with the following snippet:

let map = Foo.Map.(add_exn empty ~key:(1,2) ~data:"hello") in Foo.Map.find map (1,2)

The style you were attempting (Map.empty (module Foo)) is heavier than using just Foo.Map and requires a first class module with a comparator and comparator witness.

Foo.Tuple2 does not define these values, but Foo does via include Comparable.Make(IntTuple). Also, Tuple2, a provided Core module is not the same as submodule Foo.Tuple2. Both of them won’t work however with Map.empty.

Hope this helps!

PS:

  • You should probably mention you’re using Core when posting issues of this nature. It might help people understand your problem a bit quicker.

  • (int,int) module Tuple2 is nonsensical because modules do not accept type parameters. While this isn’t quite the same, you could define a type like this: type 'a t = 'a * (module T with type t = 'a).

  • Consider doing type t = (int * int) [@@deriving sexp, compare] to automatically generate the serializers and comparator. It requires the ppx_jane preprocessor which is easy to setup with dune.

1 Like
3

Thanks for replying! I edited the question to call out core specifically. I guess I’m still wondering whether there is any way to use Core.Tuple2 to save myself from having to type out any of that definition above? It seems unfortunate that everyone who wants to use a map of tuple has to define their own tuple module, and can’t benefit from what’s built into Core.Tuple2.

4

Perhaps the following way to create a tuple map is short enough to suit your tastes?


module M = Map.Make(struct type t = int * int [@@deriving sexp, compare] end)

let map = M.(empty |> add_exn ~key:(1,2) ~data:"hello")
5

Yeah that’s nice and short, but it sounds like the answer to my question is no. i.e. once a module has been defined (like Core.Tuple2), there’s no way to make it work as a key for Core.Map if it wasn’t created with that intention specifically?

I’m coming at this from something like clojure, where it’s fairly easy to extend existing code and ‘types’ with new functionality, even if someone else defined them. I was hoping ocaml’s module system would let me do something similar. Or maybe I’m misunderstanding something even more fundamental… :thinking:

6

I think you may be looking for the functor Tuple.Comparable:

module Int_tuple = Tuple.Comparable (Int) (Int)

As for extending modules written by others, isn’t that what you get with include? Maybe I don’t understand what you’re looking for.

7

Hmmm, that’s interesting! Those are two good leads I think; I’ll have to do more reading and experimenting.

Thank you @Levi_Roth and @struktured!

1 Like