Is there a concise/inline way to create Set values without explicitly naming their type?

Question

In most language that have parametric / generic types, there is a (type) expression you can write to mean 'Set of something'. E.g. Set<Integer> in Java.

Similarly in OCaml we have something like that for lists int list.

However, there seems to be no way to say int set in OCaml. (Or perhaps I just haven't found / figured out how).

There is no 'generic Set' type. Instead there is a Set module which contains a 'functor' called Make which you pass in another module containing definitions for a 'ordered' type.

So instead we have to do something like:

module IntSet = Set.Make(Int)
let numbers : IntSet.empty

Thus we have declared a module IntSet which contains functions to operate on Sets of int. It also contains a type IntSet.t that is essentially the equivalent of Set<Int> in Java.

That all kind of makes sense in some way. But it is a little annoying that this forces us to pick explicit names for every type of Set that we want to use in our program and define it somewhere explicitly (IntSet, StringSet, FloatSet, ...).

Is there a way to avoid this? Maybe some inline / anonymous / concise way similar to Java Set<...> to construct the IntSet module locally without giving it a name?

I tried something like this but it doesn't work.

let numbers = Set.Make(Int).empty
(*            ^^^^^^^^ unbound constructor Set.Make *)

Oddly this kind of notation does appear to work inside of an .mli file declaring the types only:

val numbers : Set.Make(Int).t

That gives some hope that it should be possible.

Answer 1

In the big picture I think this is something you might just have to get used to. The notation is a little heavier than some other languages, but OCaml modules are also much more expressive than those of other languages.

That said, you can avoid giving a name to the module using let open:

# let numbers = let open Set.Make(Int) in empty;;
val numbers : Set.Make(Int).t = <abstr>
# let morenumbers = let open Set.Make(Int) in add 14 numbers;;
val morenumbers : Set.Make(Int).t = <abstr>

At least, this works for me.

The essence is that you need to use a place in the syntax where a module name can go. In the expression syntax Set.Make(Int).t looks like a value constructor. (Or anyway this is how I interpret the behavior.)

Update

As a commenter far wiser than I has pointed out, it's good to keep in mind that this is not good style in OCaml. As I said, in the big picture you probably just want to get used to giving names to modules.

Answer 2

An important point is that it is not possible to build a set (with ln(n) query complexity) from just a type. A set is defined by both a type and a comparison function over this type. For instance, a Java's TreeSet<T> is only valid for types T that implements the comparator interface, or if the constructor is given a comparator function.

OCaml's functor based sets make this relationship obvious and visible at the type level. For instance, I can define both a set for float and temperature as float (with the physically correct comparison between temperatures)

module Float_set = Set.Make(Float)
module Temperature = struct
  type t = float
  let compare x y = match x > 0, y > 0 with
  | true, false -> -1 (* negative temperatures are hotter than positive ones *) 
  | false, true -> 1
  | false, false -> Stdlib.compare x y
  | true, true -> Stdlib.compare y x
end
module Temperature_set = Set.Make(Temperature)

and the type Temperature_set.t and Float_set.t will be distinct and incompatible even if the elements of both sets are float.

Answer 3

You have received an answer to you question whether you can avoid explicitly naming the module returned by the Set.Make functor: not really.

However it is worth knowing why you are in this position with the Set module to begin with, and that is because of the universal quantification of type variables applied to value types in module signatures. Such type variables no longer mean "some type to be inferred by the compiler"; they stand instead for "for all types". In the associated implementation module(s), the function(s) or other value with the polymorphic signature must be implemented so that the relevant type variable(s) are capable of being any type.

Take a module for a set with a signature like the following, where the 'add' function calls up some internal comparison function in order to determine the ordering of elements:

  sig
    type 'a t

    ...

    val empty : 'a t
    val add : 'a t -> 'a -> 'a t
  end

Such a signature is problematic because for the add function to be compilable under this signature, it must be polymorphic, which in turn means that the internal comparison function applied by it must also be polymorphic of type 'a -> 'a -> int. The standard library does indeed provide such a function in the form of the Stdlib.compare polymorphic structural comparison function, with some well-known downsides: namely, structural comparison is unreliable for complex data structures and cannot in practice be used to compare all things - for example, if you try to apply Stdlib.compare to a function you will get an exception. Accordingly it is generally better for the comparison function to be monomorphic - that is, you generally want different implementations of it for ints, floats, strings and so forth, or for entities of your own devising.

One way to achieve this, the one used by the standard library, is to make the element type monomorphic at the outset, so:

  sig
    type t
    type elt

    ...

    val empty : t
    val add : t -> elt -> t
  end

Now the internal comparison function can also be monomorphic, of type elt -> elt -> int. Such a module is most easily constructed using a functor applied to a struct which provides the element type and the comparison function. The type of the output module of the functor then bears a sharing constraint such as 'Set.S with type elt = [element type]': see the standard library's Set.Make functor for more.

One exception (an emergent property of ocaml's type system) to the rule about universal quantification mentioned above concerns higher order functions, in particular functions which take another function as an argument. Even though parameterised, such an argument may be passed a monomorphic function (provided in the case of a set that it matches the element type for which the set is constructed). So 'empty' could be turned into a function, possibly renaming it 'make' in consequence, which takes the comparison function as an argument and which stores the comparison function in a record or tuple for future use together with the root node of the set, resulting in a signature something like this:

  sig
    type 'a t
    type comp = 'a -> 'a -> int

    ...

    val make : comp -> 'a t
    val add : 'a t -> 'a -> 'a t
  end

However this runs up against a problem where a function takes more than one set as an argument, say in order to concatenate two sets. To work correctly it may be necessary that both sets have been constructed for the same comparison function. This requires parameterising the set with a second type parameter which holds some arbitrary phantom type representing the comparison function, which is somewhat tedious. That is in essence what the Jane Street Library's Base.Set module does.

In languages like C++ or Java, you can use generics to implement containers for the sub-set of types which have had, say, the Comparable interface or concept implemented for them. You cannot directly do that using type variables under ocaml's type system. Functors happen to be one of the more straightforward ways of achieving something similar, but it does have the somewhat verbose syntax to which you have referred.

Answer 4

If you can use Jane Street's replacement Base library instead of the standard one, it has a Set module that essentially includes a comparison as part of the type; it can take a module as an argument to functions that create a new set that you can use instead of a functor:

$ ocaml
# #require "base";;
# open Base;;
# let foo = Set.empty (module Int);;
val foo : (Base.Int.t, Base.Int.comparator_witness) Base.Set.t = <abstr>
# let foo2 = Set.add foo 5;;
val foo2 : (Base.Int.t, Base.Int.comparator_witness) Base.Set.t = <abstr>
# Set.to_list foo2;;
- : Base.Int.t list = [5]

Real World Ocaml explains more about how this works with the comparator_witness type and how to make your own modules for custom comparisons.