Why don't HashSets implement PartialOrd?

1

It's not a problem since I can always just make a struct that gives me this functionality, but from a language design perspective, I am curious why HashSet doesn't implement PartialOrd. There is a very natural partial ordering on the collections of sets: the subset relation, which could be implemented as:

impl<T: Hash + Eq> PartialOrd for HashSet<T> {
    fn partial_cmp(&self, rhs: &Self) -> Option<Ordering> {
        match self.len().cmp(&rhs.len()) {
            Ordering::Equal if self.iter().all(|t| rhs.contains(t)) => Some(Ordering::Equal),
            Ordering::Less if self.iter().all(|t| rhs.contains(t)) => Some(Ordering::Less),
            Ordering::Greater if rhs.iter().all(|t| self.contains(t)) => Some(Ordering::Greater),
            _ => None,
        }
    }
}

One could extend to the same idea to HashMap when the value type is PartialEq by replacing all(|t| rhs.contains(t)) with all(|(k, v)| rhs.get(k).is_some_and(|w| *w == *v)).

For even more flexibility, one could modify this for value types implementing PartialOrd by first comparing the underlying sets of keys and then performing a point-wise comparison of the values, but that might be getting too wild: in particular, it would conflict with the foregoing definition.

In any case, I'm just curious why the seemingly-natural definition of a partial order on sets is not part of std.

2

The same argument can be made for HashSet, and differing expectations is probably a factor.

BTreeSet compares lexicographically, not based on the subset relation. I'd agree it's not well documented.

1 Like
3

But is it a useful implementation? Or will it surprise more people than it helps?

Note that that would be a completely different version of PartialOrd from what BTreeSet<T> offers.

1 Like
5

Thanks for the thoughts, all! I asked a pretty open-ended questions, so I don't imagine there's a definitive answer, but it's useful to have a sense of how folks think about these things.

... and differing expectations is probably a factor.

Note that that would be a completely different version of PartialOrd from what BTreeSet<T> offers.

Yeah, I think differing expectations is a compelling reason. From my perspective, the lex ordering on BTreeSet is quite natural, and it's obviously impossible on HashSet<T> when one doesn't have T: Ord.

Even when T: Ord, the lex ordering obviously wouldn't be performant since the comparison would requiring constructing and sorting some temporary Vecs or something.

But I can still understand an argument along the lines of "if BTreeSet and HashSet are both going to implement a trait, the trait should mean the same thing for both structs."

But is it a useful implementation? Or will it surprise more people than it helps?

It's definitely useful for me, and I was kind of shocked that it wasn't implemented. But I don't know about anybody else's experience.

In any case, thanks again for the thoughts! The matter isn't much of a nuisance, since it's perfectly easy to accomplish the same functionality on one's own.

1 Like
6

As an aside, if you have HashSets for both sides I think you might be looking for https://doc.rust-lang.org/std/collections/struct.HashSet.html#method.is_superset?

(Mentioned because I do agree that the sub/super-set relation is useful, and thus that we should have an easy way to do it, I'm just not convinced that PartialOrd is the right way to spell that.)

2 Likes
7

Absolutely! I'm aware of that method (and its dual, is_subset), but was surprised not to see them used to implement the trait, a bit like how BitAnd is implemented by collecting intersection.

The reason I didn't use is_superset in the hypothetical implementation in my OP is performance: each call to is_superset or is_subset would make two calls to len, which is redundant, since we should check the lengths at the outset in order to determine which relationship to test.

Actually, performance is part of why I asked my question: we can just call is_superset or is_subset, but if an ordering is what we're after, that's not quite optimal.

Also, speaking of BitAnd (and BitOr), this is part of why I was surprised that PartialOrd is not implemented: from a mathematical perspective, the Boolean & and | operations on e.g. a Boolean or Heyting algebra are the join and meet respectively on the partially ordered set of truth values. And the currently existing implementations of BitAnd and BitOr are exactly the right ones to be mathematically compatible with the natural implementation of PartialOrd for HashSet<T> (i.e. the intersection of two sets is the greatest lower bound on the two sets under the subset parital ordering, etc.). In this sense, the ordering I ask about is really just an extension of already-implemented semantics for HashSet.

Anyway! I'm not trying to argue that anything should change – just explaining my point of view in asking the question! It's clear that the PartialOrd I am asking about is not as intuitive for most people as I thought it was, and that is good reason for not implementing it.