Base: design of empty in Map/Set/Hashtbl

Learning
1

Hello all,

Currently working through the awesomely fun Real World OCaml, 2nd ed., which, among other things, is introducing me to the Base library. (Normally I use a different standard library.)

I noticed that Base defines these empty-making functions with “comparator module” inputs for Set/Map/Hashtbl/etc. E.g. Base wants you to do this:

utop[6]> open Base;;
utop[7]> module Dict = Map.M (String);;
module Dict :
  sig type nonrec 'v t = (string, 'v, String.comparator_witness) Map.t end
utop[8]> let empty = Map.empty (module String);;
val empty : (string, 'a, String.comparator_witness) Map.t = <abstr>

As opposed to what I think of as the normal Stdlib-y way to do it, which is to grab the empty value out of the module you defined via the Map.Make module functor:

utop[5]> module Dict = Stdlib.Map.Make (String);;

...etc...

utop[6]> let empty = Dict.empty;;
val empty : 'a Dict.t = <abstr>

I was wondering what the design rationale behind that is. If Jane Street is doing it, lol, it’s pretty much guaranteed there’s a compelling reason. Yet I can’t think of a reason to design empty in that way across all these modules, off the top of my head.

Thanks as always!

1 Like
2

Base and Core nudge you in the direction of the functorless approach because we found that big functors (Comparable.Make was the main one) were a cause of code bloat and slower compile times. I think I remember hearing that 30% time spent in the typechecker was spent comparing module signatures generated by Comparable.Make, Map.Make and its ilk. Now, most of the improvement was by getting rid of accessor functions, (e.g. My_type.Map.find), and Core still includes the functors and exports the empty value, but that’s mostly for backwards compatibility concerns (the values produced by successive calls to the empty function will yield physically different empty maps, but the empty value yielded by the Make functor is a singleton value)

6 Likes
3

Fascinating. So would you say there has been slash is a general push to break large module functors up into individually-defined functions and values that are parameterized on a module?

4

I’d say that there’s a push to functors as little as possible.

It’s better to have code that uses things like Set.add instead of String.Set.add, because when you eventually want to change your code from using “string” to e.g. “Username.t”, you don’t need to chase through all the functions and swap out “String.Set.” to “Hostname.Set.”

One issue with functors is that they tend to be infectious: if some functionality is only available through a functorized API, then callers need to be functorized as well, and their callers, and so on

5 Likes
5

I assume another advantage of first-class modules is that they will work better with the intended future state of modular implicits. Would just need to delete the explicit FCM argument and let it be inferred.

2 Likes
6

(a bit off-topic, but I loved your Signals & Threads episode on UI stuff)

2 Likes