# Are poker hands Ord or PartialOrd?

Hello,
Im trying out this exercise and there is something in that description that doesn't really make any sense to me.
Specifically these two points:

``````* Ord types form a total order: exactly one of a < b, a == b, or a > b must be true.
* Poker hands do not conform to a total order: it is possible for two hands to be non-equal but have equal sort order. Example: "3S 4S 5D 6H JH", "3H 4H 5C 6C JD".
``````

Why do they think `"3S 4S 5D 6H JH", "3H 4H 5C 6C JD"` are non-equal? They are equal. That is a split pot!!
And since that is true, does it means poker hands DO conform to a total order?

Can someone provide me hand samples and explain to me why they do or do not conform to total order?

2 Likes

I'm not familiar with poker, but I think what the comment and what you understand under "equality" of a hand are not the same.

The documentation of Ord must be consistent with the implementation of Eq.

If Eq is defined for a hand as the specific cards it contains, then the two hands in the comment are not equal.

If Eq is defined for a hand as the equality of some projection onto types of whatever "split pot" is, then the two hands would be equal.

So it all comes down to the implementation of Eq and the requirement of Ord to be consistent with it.

2 Likes

Think in terms of a set. Equal is only for the same item taken out of the set. If not then only partial.

This is where it is important to define what "equal" means.

In Rust, "equal" typically means "value equality" (i.e. two hands are equal if they have the exact same set of cards). This makes testing a lot easier because you can use `assert_eq!()`, and people won't be surprised when hands with different face values are reported as being equal.

The other definition of "equal" is "identity" (i.e. when two `Rc<Foo>`'s point to the same `Foo` object), but poker cards are fungible so identity equality isn't really helpful here.

On the other hand, it sounds like you are interpreting "equal" in the context of who would win.

If it were me, I probably wouldn't use the `Ord` and `PartialOrd` trait to rank different poker hands. Instead, I'd make a bespoke function which returns some sort of `enum Winner { Player1, Player2, Draw }`.

To make things worse, if you used `Eq` or `Ord` to compare poker hands, common collections like `HashSet` and `BTreeMap` will start behaving very strangely because they use the `Eq` and `Ord` traits when reasoning about the keys.

The `Hash` trait would also be broken with this interpretation of `Eq` unless you create a clever custom implementation. There is the constraint that when two items are equal, they must hash to the same value.

15 Likes

I agree with simply having a method like `compare_value_to` which may even return an `Ordering`.

Another possibility is to define another type such as:

``````enum HandValue {
...
TwoPair{higher_rank: Rank, lower_rank: Rank},
...
StraightFlush{highest_rank: Rank},
...
}
``````

then your hands can implement `fn value(&self) -> HandValue` and `HandValue` can implement `Ord`.

8 Likes

I really like that `HandValue` approach.

You can define `Eq` and `Ord` on a `HandValue` because it makes logical sense for two `HandValue::TwoPair { Ace, Four }` values to be compared or hashed without the "two sets of cards that are different but still compare equal" problem you have when representing cards directly.

It also gives you something you can print to the user, which is nice.

5 Likes

You could define several orders for poker hands. I assume we're talking about an order that reflects the "value" of the hand. Such an order where some items may be ranked equally is, mathematically speaking, a "total preorder" (see Wikipedia here and there).

But there are more ways to define orders for poker hands, for example you could lexicographically order them, etc.

That depends on definition of equality. Mathematically they are not the same objects (i.e. not "equal" in the mathematical sense), but they are in the same equivalence class, if you consider their value. Thus you could say they are "equivalent" in regard to their value (see also Wikipedia on Equality and Equivalence).

This is partially reflected in the documentation of `std::ops::Eq` where it says:

Trait for equality comparisons which are equivalence relations.

It says "equality comparison" but clarifies that actually equivalence relations are meant.

I started a longer thread a while ago on Traits in `std::cmp` and mathematical terminology, in which I wrote:

The important point here is: Whether `Ord` is a "total order" or a "total preorder" (the latter allows two different objects to be ranked equal, which you would need for poker hands) depends on how `==` is implemented in the particular case. When `==` is implementing mathematical equality, then `Ord` can't be a total preorder. However, if you implement `==` in a way that two different (mathematically non-identical) values may return true when compared with `==`, then `Ord` is (mathematically speaking) not a total order but a total preorder, i.e. exactly what you need for the poker hands!

Theory aside, let's look at the return values of `Ord::cmp` and `PartialOrd::partial_cmp`:

• `fn cmp(&self, other: &Self) -> Ordering`
• `fn partial_cmp(&self, other: &Rhs) -> Option<Ordering>`

With `Ordering` being defined as:

``````#[repr(i8)]
pub enum Ordering {
Less,
Equal,
Greater,
}
``````

So `Ord::cmp` may return one of three values:

• `Less` (poker hand is worse)
• `Equal` (poker hand has equal value)
• `Greater` (poker hand is better)

(which is what you need, IMHO).

The method `PartialOrd::partial_cmp`, in turn, would return one of four possible values:

• `Some(Less)` (poker hand is worse)
• `Some(Equal)` (poker hand has equal value)
• `Some(Greater)` (poker hand is better)
• `None` (we can't compare the poker hands, e.g. because perhaps one hand is invalid?)

Now the catch is that according to the documentation:

• Implementations of `Ord` must be consistent with the `PartialOrd`implementation.
• The [method implementations of `PartialOrd`] must be consistent with each other and with those of `PartialEq`.

Thus if you allow `Ord` to return `Ordering::Equal` for some non-identical values (e.g. `"3S 4S 5D 6H JH"` and `"3H 4H 5C 6C JD"`), then you must also implement `PartialOrd` in such a way that the equality operator (`==`) will return true when comparing these two hands.

It's perfectly fine to do that! However, you will lose the ability to compare poker hands in a stricter sense (e.g. if you need to check whether two hands consist of the same cards in arbitrary order, or of the same cards in the same order).

Edit: And you will lose the abilitity to treat two "equivalent hands (in regard to their value)" as two separate items in a `HashSet`, for example, as pointed out by @Michael-F-Bryan previously. `Hash` and `Eq` must always be implemented consistently.

So it's ultimately your choice what to do. You could decide to make the `==` operator work on the equivalence relation regarding equal value of the hands (i.e. return true for different hands which have the same value), or you could follow @tczajka's approach of not using `Ord` (and instead writing your own `compare_value_to` method), or to use an `enum HandValue`.

Another option would be to use the newtype pattern, where you wrap a poker hand in another type and then implement `Ord` on that type.

I think that the Rust documentation still requires some overhaul in regard to precise terminology and giving some hints to avoid confusion. Maybe if I have some time, I will make a proposal on how to clean that up.

6 Likes

Technically this constraint only holds when you also implement `Eq` (in addition to `PartialEq`). Though I guess you should implement `Eq`.

Edit: I just noticed `Eq` is a supertrait of `Ord`, please disregard my comment.

1 Like

Yeah, that's a tricky one.

On one hand, the docs need to be unambiguous and tell people what they can/can't rely on. Especially when it has an effect on correctness or behaviour (e.g. keys in a `HashMap`).

On the other hand, if we made it precise (using proper mathematical concepts like total preorder and equivalence relations, etc.), it'll be like whenever you look up a physics or mathematics concept on Wikipedia and need a masters degree just to understand the words and a PhD for it to be useful.

Arguably, the second situation is just as bad because ambiguous documentation is just as useless as something that's confusing or requires knowledge that most readers won't have.

But perhaps I'm going off on a tangent here 3 Likes

The "value" of a hand imposes a weak order on the set H of all poker hands. That is, there exists a relation < in H that is transitive, irreflexive, and antisymmetric: for all a, b in H,

• a < b && b < c => a < c
• !(a < a)
• a < b <=> !(b < a).

These conditions imply that there exists a relation Eqv(a, b) <=> !(a < b) && !(b < a) that partitions H into equivalence classes: hands that have the same value but are not necessarily equal. Furthermore, the weak order imposes an unambiguous total order on the set of equivalence classes (ie. hand values), as expected.

Unfortunately, Rust does not have a `WeakOrd` trait. Every weak order is also a partial order, but implementing `PartialOrd` is unsatisfactory and even misleading: hands with equal value are equivalent, not incomparable! On the other hand, implementing `Ord` would mean that `Eq` would have to regard equivalent hands as equal, which would be semantically wrong. (And `Hash` would naturally have to agree with `Eq`.)

Things being how they are, I would implement `Eq` but neither `Ord` nor `PartialOrd` on poker hands; rather I’d just have a `value` method that returns something that is `Ord`.

In general, the concept of a weak order is very useful; indeed most algorithms and data structures that depend on an ordering (sorting, partitioning, search trees, etc) work just fine with only a weak rather than a total order, which is why eg. in C++ they only require a weak order.

2 Likes

I don't think precise and intelligible are mutually exclusive here. The problem is that the documentation does already contain mathematical terms such as "partial ord(er)", "equivalence relation", "total order", etc. These terms must be used correctly and unambiguously.

In addition, things should be explained in a "down to earth" fashion such that it's possible for someone without mathematical background to understand usage properly. I.e. I don't want to make the documentation more precise at the cost of being more difficult to read, but I would like it to be

• correct
• unambigious
• easy to understand for someone who doesn't know about the mathematical terms
• easy to understand for someone being used to the mathematical terms

If I understand it right, then (non-strict) weak orders are essentially the same as total preorders (Wikipedia), but I'm not really an expert on that.

One could consider `Ord` to be a weak order, see:

That's where the documentation is a bit misleading.

If `Eq` describes an equivalence relation (and not equality), then `Ord` describes a weak order (i.e. a total preorder). Now one could argue whether `Eq` means equality or equivalence. Let's review the docs again:

### Trait std::cmp::Eq

``````pub trait Eq: PartialEq<Self> { }
``````

Trait for equality comparisons which are equivalence relations.

I'm not sure how to interpret that sentence. Maybe it means that it must only be used for equality comparisons and the second part of the sentence ("which are equivalence relations") is just redundant information. But that can't be. Let's look at `PartialEq`'s docs:

### Trait std::cmp::PartialEq

``````pub trait PartialEq<Rhs = Self>
where
Rhs: ?Sized,
{
fn eq(&self, other: &Rhs) -> bool;

fn ne(&self, other: &Rhs) -> bool { ... }
}
``````

Trait for equality comparisons which are partial equivalence relations.

If `Eq` really is to implement mathematical "equality" only, then the same would hold for `PartialEq`, but I don't think that "equality" here means equality in the mathematical sense.

In the wild, there will be implementations where using the equality operator on several different objects/values returns true (see Playground for an example in `std`). I would thus conclude that `Eq` can be used to describe any equivalence relation (and not just "equality"). The "equality operator" (`==`) will behave according to that equivalence relation (and not regarding true equality/identity).

I agree on that. But the situation is even more wicked: `PartialOrd` requires that:

The methods of this trait must be consistent with each other and with those of `PartialEq`. The following conditions must hold:

1. `a == b` if and only if `partial_cmp(a, b) == Some(Equal)`.
2. […]

Thus hands with equal value would need to be

• equivalent (i.e. `partial_cmp(a, b) == Some(Equal)`) when they are equal and
• incomparable (i.e. `partial_cmp(a, b) == None`) when they are not equal but equivalent regarding their value.

I would thus concur that using `PartialOrd` here as a solution is a bad idea.

2 Likes

@AlwaysLearning I hope my comments on Rust's documentation didn't make things more confusing than before.

There are actually two different levels of the discussion:

• Terminology (i.e. what is "equality" or "equivalence", etc.)
• What to do best (i.e. how to solve the problem in Rust)

Let's forget about terminology, and focus on the second part.

Summarizing, one of the following approaches might be best:

• Use two different types for poker hands (e.g. `PokerHand`) and their value (e.g. `PokerHandValue`), and provide a method (e.g. `value`), which returns the `PokerHandValue` for a given `PokerHand`. You can implement `Ord` for `PokerHandValue`. Now `"3S 4S 5D 6H JH"`, and `"3H 4H 5C 6C JD"` could be non-equal hands, but having an equal value.
• Do not use `Ord` and `PartialOrd` at all. Instead provide a method with a name of your choice (e.g. `cmp_by_value`, or `compare_value_to` as suggested by @tczajka), for example, which may return an `Ordering`.

Other, less preferred (and maybe non-idiomatic) options could be:

• Make `==` return true when comparing two different hands with the same value. Like I said, I think this is possible, but it will make it impossible to store two different hands with the same value in certain data structures because they will compare as "equal" (even if they consist of different cards). Maybe it's not a good idea, but if you go that way, you can implement `Ord`.
• Use the newtype pattern, where you wrap a poker hand in another type and then implement Ord on that type. Maybe this option is most confusing, especially if you are still learning.
4 Likes

Wow! Thank you all for the in-depth answers as expected by this community.

There is so much to say in regard to these traits that I dont know where to begin. I have read and re-read your comments. So, I'll just make statements in random order.

• `Eq` and `PartialEq` tell whether two instances are same or not. That's it. They have nothing to do with `<` or `>`.
• `Eq: PartialEq` means types are identically same (`a == a`) in addition to being symmetric (`a == b` implies `b == a`) and transitive (`a == b` and `b == c` implies `a == c`).
• As for `PartialEq`, users decide when two instances have value equality. (Like `clone()` where we get to decide how to clone instances)
• `PartialOrd` means two instances of a type may not be comparable. Hence, `partial_cmp()` returns `Option<Ordering>`.
• `Ord` means all instances of a type are comparable. Hence, `cmp()` returns `Ordering`.

As to poker hands, they are `Ord` because all hands are comparable (win, lose or split/equal). What I find odd is, hands are `Ord` but because of `Ord: Eq + PartialOrd`, they are also `PartialOrd`. This trait bound confuses me. For two reasons:

1. Why is my type supposed to impl both? Is it not enough for `Ord` to return a non-`Option` value ie `Ordering`?
2. Also why `Eq`? `cmp` will return Ordering::Equal if they are same in value. What am I supposed to do in `PartialEq` that is brought in by `Eq`?

I will go ahead and what I have so far.

``````struct Hand {
sorted: [Card, 5]
}

impl Hand {
fn is_royal_flush(&self) -> bool {}
fn is_straight_flush(&self) -> bool {},
...
}

impl PartialOrd for Hand {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(self.cmp(other))
}
}

impl Ord for Hand {
fn cmp(&self, other: &Self) -> Ordering {
// This is complicated. I handle hands on a case-by-case basis.
// For eg., I return Ordering::Equal if self and other are royal flushes.
// For other hands, if they are same in value (like straight flush and flush), then I check for higher cards.
// For other hands, I return Ordering::Less if self is flush and other is royal flush.
// And so on.
}
}

impl PartialEq for Hand {
// Im hitting a brick wall here. What am I supposed to do here?
}
``````

I felt I was close but then @jbe and @tczajka suggestions to create `value() -> Ordering` brought me back to square one. If Im being honest, I dont know why that suggestion is better than what I have.

My stance is that `Eq` and `PartialEq` denote an equivalence relation (or partial equivalence relation if `Eq` is not implemented), not necessary equality or "being the same" as in being identical. But there may be other opinions on that.

However, `Eq` and `PartialEq` are related to `<` and `>`, because if two values `a` and `b` compare as equivalent (i.e. if `a == b`), then `a < b` must be false. That is because the documentation of `PartialOrd` demands:

The methods of this trait must be consistent with each other and with those of `PartialEq`. The following conditions must hold:

1. `a == b` if and only if `partial_cmp(a, b) == Some(Equal)`.
2. `a < b` if and only if `partial_cmp(a, b) == Some(Less)`
3. […]

Thus, if `a == b` (due to an implementation in `PartialEq`), then it must not happen that `a < b`, because `a == b` implies that `partial_cmp(a, b) == Some(Equal)` which cannot be `Some(Less)` at the same time.

I would phrase it differently: `Eq` implies that `a == a` (reflexivity), i.e. that the `==` operator describes an equivalence relation (and not just a partial equivalence relation).

I would agree here.

Yes, and in that case `a < b`, `a <= b`, `a == b`, `a >= b`, `a > b` are all false! (But `a != b` is true!) (Playground).

Yes, but comparing two non-identical values (such as `-0.0` and `0.0`) using the `==` operator might still return true (Playground).

Yes, unless you have hands that are invalid, e.g. hands with a card missing.

This is to ensure that bounds which expect a type type `PartialOrd` can also accept all types that are `Ord`. It has to do with how Rust's type system work. `PartialOrd` needs to be a supertrait of `Ord`. Rust doesn't allow to automatically implement `PartialOrd` based on your `Ord` implementation, so you have to do it manually, unfortunately.

I don't understand what you mean. Can you rephrase the question or elaborate more?

You need to make a choice first. Do you want to implement `Ord` for `Hand` in such way that the ordering reflects the value of the hand? If yes, that corresponds to alternative 1 below; if no, then it corresponds to alternative 2 below.

## Alternative 1

If yes, then this means `a == b` has to be true for two different hands `a` and `b` if their value is the same. (That's okay but may restrict you if you later want to use the `==` operator in a different fashion.) If you go this way, you can implement `PartialEq::eq` by just forwarding to `Ord::cmp`. See the following Playground:

``````use std::cmp::Ordering;

struct Card { /* … */ }

struct Hand {
sorted: [Card; 5], // maybe use `Vec<Card>` here?
}

impl Hand {
fn is_royal_flush(&self) -> bool { todo!() }
fn is_straight_flush(&self) -> bool { todo!() }
/* … */
}

impl PartialOrd for Hand {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(self.cmp(other))
}
}

impl Ord for Hand {
fn cmp(&self, other: &Self) -> Ordering {
todo!()
}
}

impl PartialEq for Hand {
fn eq(&self, other: &Self) -> bool {
self.cmp(other) == Ordering::Equal
}
}

impl Eq for Hand {} // we can implement this because `a == a`
``````

Note that `PartialEq::eq` must behave according to your `Ord::cmp` implementation! By writing `self.cmp(other) == Ordering::Equal` in the body of the `eq` method (as in the above example), this is guaranteed.

## Alternative 2

If you decide you want a different behavior of the `==` operator, then you cannot proceed like that, and instead you would need to pick one of the following choices:

1 Like

If it were me, I would rely on the behaviour of `#[derive(PartialEq, Eq, PartialOrd, Ord, Hash)]` instead of trying to implement the traits manually. That way you can make sure things will be ordered correctly just by looking at how their definitions are ordered.

First, I would define the basic types you need for representing a card. Note that there is no ordering between suits in poker, and therefore we don't derive `Ord` (and `PartialOrd`) for the `Suit` and `Card` types.

``````#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
pub struct Card {
suit: Suit,
rank: Rank,
}

#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
pub enum Suit {
Hearts,
Clubs,
Diamonds,
}

#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub enum Rank {
Number(usize),
Jack,
Queen,
King,
Ace,
}

impl Rank {
pub fn from_number(n: usize) -> Option<Self> {
match n {
1 => Some(Rank::Ace),
2..=10 => Some(Rank::Number(n)),
11 => Some(Rank::Jack),
12 => Some(Rank::Queen),
13 => Some(Rank::King),
_ => None,
}
}
}
``````

Next, I would define the different kinds of hand you can get (pair, straight, etc.). Note that the ordering of fields and the traits we derive are important here.

``````#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub enum HandValue {
HighCard(Rank),
Pair(Rank),
TwoPair {
high_card: Rank,
other: Rank,
},
ThreeOfAKind(Rank),
Straight {
highest_value: Rank,
},
Flush {
high_card: Rank,
other_cards: [Rank; 4],
},
FullHouse {
triple: Rank,
pair: Rank,
},
FourOfAKind(Rank),
StraightFlush {
highest_rank: Rank,
other_cards: [Rank; 4],
},
}
``````

(Note: As @KSwanson's comment points out, this could be simplified by making `Flush` hold a `[Rank; 5]` and skipping the `high_card`/`other_cards` business)

Finally, we can define `Hand` and a way to compare two hands. Note that I've derived `PartialEq` and `Eq` for `Hand` because we can always check whether two hands have the same cards in them.

The `value()` method is where you would look at the hand and figure out whether it's got a pair or straight flush or whatever.

``````#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
pub struct Hand([Card; 5]);

impl Hand {
pub fn value(&self) -> HandValue {
todo!("Figure out what type of hand the player has");
}
}
``````

For convenience, I'd throw in a `FromStr` impl which lets you parse something like `"3H 4H 5C 6C JD"` into a `Hand`.

``````impl FromStr for Hand {
type Err = InvalidFormat;

fn from_str(s: &str) -> Result<Self, Self::Err> {
todo!("Parse a string like '3H 4H 5C 6C JD' into its 5 cards");
}
}

#[derive(Debug)]
struct InvalidFormat;
``````

Finally, we can start checking which hand is better.

``````fn main() {
let person_1: Hand = "3H 4H 5C 6C 7D".parse().unwrap();
let person_2: Hand = "4S 5D 6H 7H 8C".parse().unwrap();

// the two hands have different cards
assert_ne!(person_1, person_2);

// checking ordering directly is a compile error
// assert!(person_1 < person_2); // uncomment me

// however, we can check whether they have the same
assert!(person_1.value() < person_2.value());
}
``````

All the above code is on the playground.

Note that besides the `todo!()` bits, that was all I needed to do. By ordering my enums so that the lowest ranked variant comes first and variants like `HandValue::TwoPair` have fields ordered so the tie-breaker is compared first (e.g. if multiple people have two pairs, we'll first compare their `high_card` field before the `other`) I was able to let the compiler generate the tricky implementations.

Also, regarding your `is_royal_flush()`-like methods, there is a really nice blog post which explains why the `value()` way of doing things is superior... "Parse, don't validate".

8 Likes

I like your approach. It just doesn't teach how to implement `Ord` yourself (which might come in handy in other scenarios).

You can really go either way. The only downside of implementing `Ord` directly for the hand is that you will be restricted in how you can use the `==` operator and in how you can store hands in certain data structures such as hash tables.

In general, I prefer to use derives because humans are bad at writing repetitive code. Plus, whenever readers see a `#[derive(PartialOrd)]` they just need to look at the definition to understand how things are ordered.

To me, the presence of a `#[derive(Ord)]` just indicate that comparisons are well behaved and obvious, with no NaN-like funny business. You can use the same "funny business" rule of thumb when deciding whether `Eq` is appropriate.

Sorry to jump in here, I was just confused about something:

``````#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub enum HandValue {
HighCard(Rank),
Pair(Rank),
TwoPair {
high_card: Rank,
other: Rank,
},
ThreeOfAKind(Rank),
Straight {
highest_value: Rank,
},
Flush {
high_card: Rank,
other_cards: [Rank; 4],
},
FullHouse {
triple: Rank,
pair: Rank,
},
FourOfAKind(Rank),
StraightFlush {
highest_rank: Rank,
other_cards: [Rank; 4],
},
}
``````

For `Flush` and `StraightFlush`, why do you separate `highest_rank` from `other_cards`? Is it just a convenience?

And separately (or maybe not), will the derivation of `Ord` Do The Right Thing when `highest_value` are the same? I.E., will "QS 9S 7S 3S 2S" "QS 9S 7S 4S 3S" be considered greater than "QD 9D 7D 3D 1D" "QD 9D 7D 4D 2D" automatically? And if so, why not just have a single 5-length `Rank` array?

Note: edited to fix my sample poker hands because I forgot that aces are high in poker That's a good point!

In retrospect, I probably should have used a `[Rank; 5]` for both and then just require `Hand::value()` to make sure the array is sorted in descending order. The two versions are identical as far as the comparisons are concerned, and splitting the highest card out like that was probably unnecessary.

In theory, I could have also created a `SortedRanks` type which contains a `[Rank; 5]` which is always in descending order (thanks to its constructor) and has helper methods like `high_card()` to make printing "ace high flush" to the screen.

2 Likes