Polymorphic equality safe to test for emptiness of set?

Learning
1

I wonder if it’s safe to use polymorphic equality (=) to test for an empty Set. I.e. can I assume that the following always evaluates to true, or is this (in theory) implementation dependent:

module IntSet = Set.Make(Int);;
IntSet.remove 7 (IntSet.add 7 IntSet.empty) = IntSet.empty;;

- : bool = true

And which part in the documentation would tell me?

I learned that polymorphic comparisons come with surprises, such as when attempting to compare a rational number:

#require "zarith";;
Q.of_ints 1 2 < Q.of_int 1;;

- : bool = false

A warning is given here in the documentation. (edit: the link doesn’t seem to work right now, here is another link to the warning in the documentation)

I ask mostly out of curiosity, as I see there is an explicit Set.S.is_empty function, which seems to be more idiomatic?

Related: Removing polymorphic compare from Core

2

It’ll work correctly for <= 2 elements, but once you go over that there’s no guarantee it’ll work correctly (since multiple trees map to the same Set), so it’s a good idea to always avoid it.

1 Like
3

That is (a bit) surprising to me, though I suspected this can happen.

I assume that a = b ⇒ equal a b, even if the reverse isn’t true.

Maybe it would be good to add a warning to Set.S.equal, Set.S.compare, Map.S.equal, Map.S.compare to always use these functions instead of polymorphic equality, like it’s done in Q’s documentation? Or maybe it’s redundant as experienced programmers will know this.

4

Kind of, we’d need to all add that to all of our modules. Also if you use = you are unlikely to go read that doc string (though you could catch it in passing).

In a more sophisticated language experience I would not like to get rid of polymorphic comparison like many people want (I often find useful, if only to use it to implement a M.equal) but have a warning that tells me I’m using it on two M.t while M.equal exists so that could be a bug.

In addition an opt in attribute on M.equal could indicate not to warn so as to retain the readability of comparison oprators on those values where comparison gets specialized e.g. you’d have it on {Float,Int}.{equal,compare}.

(but I guess that once you have that detection machinery you could also simply specialize the = :–)

5

It is in theory implementation dependent, even if in practice this aspect of the implementation is unlikely to ever change. The comparison evaluates to true because due to the implementation of Set there is only one way to represent the empty set, but there is no theoretical guarantee that that will always be the case.

Unless I missed something, it seems the main pitfalls of using polymorphic comparisons are not stated in the manual, it would be nice to add them.

Using is_empty is indeed better and more idiomatic.

Cheers,
Nicolas

2 Likes