Examples of using Base Map

It’s definitely true that the documentation around Map is insufficient. We’re working on it, and I also hope to refresh the chapter in RWO to cover the way Maps now work in Base (and will soon work in Core as well.)

It’s definitely most convenient if you use Base’s Int module, but it’s easy enough to do it with your own module.

module Foo = struct
   module T = struct
     type t = int * int
     let compare x y = Tuple2.compare Int.compare Int.compare
     let sexp_of_t = Tuple2.sexp_of_t Int.sexp_of_t Int.sexp_of_t
   include T
   include Comparable.Make(T)

Gives you a module Foo with the appropriate comparator in it, and then this:

let m = Map.empty (module Foo)

lets you create a module keyed by Foo. You need to write a sexp-converter and a comparison function for this to work, because maps both need comparison and the ability to serialize the key for generating useful errors. It’s of course nicer to do this with the appropriate PPXs:

module Foo = struct
    module T = 
       struct  type t = int * int [@@deriving sexp_of, compare]  end
    include T
    include Comparable.Make(T)

There’s no soundness issue, because the functor mints a fresh type each time it’s called on a different input module, ensuring that different comparison functions have distinct type witnesses.


1 Like

This is a cool encoding, it may be worth a blog post : )
The only downside is that it is a bit user heavy to create the keyed module. Is it possible to make it as lightweight as just feeding a comparison function while stay

@bobzhang seeing you’re an Admin consider moving your more in-depth discussion into a thread with an appropriate title. (Discourse allows moving posts to a new thread.) I assume more people are interested in the more in-depth discussion you had with Yaron here but might not see it because it’s “hidden” in this Newbie question thread :slight_smile:

PS. I haven’t yet tried using Map after I got things to work with List.Assoc (perf is not an issue right now) but I’ll get to it eventually. Definitely big thanks for the example @Yaron_Minsky :+1:

FWIW I find it sometimes a bit confusing to trace what the examples in RWO refer to; is it Core, is it Base, what version, etc. I think co-locating this kind of more tutorial-style documentation with the actual API documentation might be an approach worth considering.

Playing around with it a little, any idea why

module M = struct include (val Base.Comparator.make ~compare:(-) ~sexp_of_t:(fun _ -> Sexp.Atom "dummy")) end
let m = Base.Map.empty (module M)

works but

let m = Base.Map.empty (module struct include (val Base.Comparator.make ~compare:(-) ~sexp_of_t:(fun _ -> Sexp.Atom "dummy")) end)

complains of

Error: The type comparator_witness in this module cannot be exported.
Its type contains local dependencies:

Because there is an existential type and the module must be bound (as in your first case) before we can access its components. You can find an explanation in this article page 7 in the section on Path Elaboration.

1 Like

Wow, a great answer with an exact reference! Kudos.

I guess first class modules are more counter-intuitive than I realized, since beta reduction doesn’t work as expected.

Modules have never been stable by substitution, first class modules don’t really change that.

For example, in this, you can’t substitute M by its value (try to imagine what would be the type of a).

module M : sig type t val x : t end = struct .... end
let a = M.x

Fascinating. I guess it shouldn’t be surprising that the thing preventing module substitution is precisely that which separates modules from records, that being their contained types (which need static paths).

Getting back to the topic of the new Base Map, here’s how I see it right now:


  1. No need to come up with new module names.
  2. No need to construct map modules.
  3. Can’t accidentally use structural comparison.


  1. Extra complexity of library code.
  2. Still need to construct key comparison modules (something that could be done with anonymous modules in the functor method).
  3. Further incompatibility with rest of ecosystem.
  4. More dynamic nature (storing the comparison module in the data structure) means Flambda possibly has less opportunity to inline.

This actually reminds me a bit of Chris Okasaki’s approach in https://github.com/chrisokasaki/scads/blob/e78233ac6a787b7c66b44cd6139392418b214eb9/design/heaps.md#problem-1-dont-mix-two-different-orderings-in-the-same-heap (a heap data structure which stores a reference to its ordering module when it first constructs a heap).

1 Like

It’s worth noting, the type discipline works without actually storing the comparison function in the data structure. See Map.Tree for a version of the data structure with the same type discipline, but no stored up function.

It seems like a mistake to presume what Flambda would do with this kind of code. It’s not at all clear to me what inlining might be possible with these types, though the Flambda devs might have more to say on the matter.

I’m not especially compelled by the compatibility argument. After all, functor-specialized maps aren’t really natural as data-interchange types anyway. (Base’s maps are better for this purpose, since they’re polymorphic.)

I wasn’t talking about data compatibility here, but rather about the compatibility of Base with the rest of the ecosystem from the user’s perspective. Since the main introduction to OCaml is now RWO via Base/Core, the more incompatibilities a user encounters as he/she meets the rest of the OCaml ecosystem, the harder it’ll be for said user to become comfortable with OCaml. It feels like we’ve taken one step forward with jbuilder becoming the de facto build system, and then one step back with introducing this new break with the rest of the language.

As one potential example, a user coming to OCaml from RWO may be completely unfamiliar with applying functors since they’re essentially unnecessary in the new Base world. I realize that RWO covers them, but they’re not required for daily use in Base and so may be skipped, similar to the chapter on objects.


I don’t think this is true. Using Base in a serious way pretty much requires the use of functors. Indeed, Maps in particular requires the use of Comparable.Make to build the modules that go into the first-class modules.

More generally, I don’t have a clear sense of what incompatibility you’re concerned about here.



Good point. To be picky though, you can define the module using only a function (Comparator.make) and first-class modules.

IMO, RWO is now the main gateway into the language (the other one perhaps being ReasonML). I therefore think it’s useful to consider, when modifying Base/Core, whether it’s a good idea to switch paradigm to something that isn’t used by the rest of the community, because that’s the direction new users will follow. In the case of jbuilder, the new paradigm was clearly superior to everything that existed previously. I don’t care if new users aren’t familiar with the intricacies of _tags files, because there’s pretty much no reason to go back to that Jurassic era. In the case of standard libraries, I’m concerned about introducing brand new paradigms. A conceptual compatibility that existed between the standard library and Core/Base has been removed by the switch to first class modules, and I don’t see the standard library following suite because the advantages of this approach aren’t overwhelming. So we’re dealing with a bigger inter-library chasm forming on the main path of new users to the language. I don’t expect Jane Street to change their approach here though – I’m just voicing my concern.

The philosophy behind Base is pretty clear: it’s not attempting to hew close to the stdlib, and really never has. Instead, it’s trying to cut clear, consistent, and useful APIs, and to do so in a way that minimizes the pain points and misfeatures of the language, like polymorphic comparison and hash functions.

People who want to maximize API similarity to the stdlib should likely look elsewhere.


Am I correct in understanding that things work this way in Core 0.10.0?

Yup. The documentation for 0.10 isn’t up yet, so I can’t point you at it, but it should be up in the next few days.

Note that the docs for v0.10 are now up, and that core_kernel’s doc for Map includes some examples: https://ocaml.janestreet.com/ocaml-core/latest/doc/core_kernel/Core_kernel/Map/

1 Like

Much nicer than Map.Make in the standard library!

What are the advantages of this approach, compared to simply storing functions compare and sexp_of_t in a record when creating a map (provided via parameters to Map.empty() etc.)?

compared to simply storing functions compare and sexp_of_t in a record when creating a map (provided via parameters to Map.empty() etc.)

That would most likely make the Map type unsound, especially when using union/diff functions. Base Map/Set nicely avoids that by minting fresh type on creation.

Ah, brilliant! One thing I initially overlooked is that the module is stored as a phantom type statically, which makes everything quite convenient.