Ord and Eq instances for complex types

newer
Re: [Haskell-beginners] recursion...

older
Re: [Haskell-beginners] recursion...

Mike Meyer

18 Oct 2011 18 Oct '11

9:13 p.m.

I'm working on a problem dealing with poker hands, and need to rank them. The Ord instance seems like a natural for this, but the code came out with a lot of repetitions in it. To wit, given suitable definitions for Rank, Suit and Card, I define a Hand as: data Hand = HighCard [Card] | PairOf Rank [Card] | TwoPair Rank Rank [Card] | ThreeOfAKind Rank [Card] | Straight [Card] | Flush [Card] | FullHouse Rank Rank [Card] | FourOfAKind Rank [Card] | StraightFlush [Card] deriving (Show) [N.B. - the single or double rank is the Rank of the cards participating in that type of hand, and is compared before the rest of the cards, so AQQJT is not as good a hand as KK321 - a pair of kings beating a pair of queens.] Eq winds up looking like: instance Eq Hand where h1 == h2 = cards h1 == cards h2 where cards (HighCard h) = h cards (PairOf _ h) = h -- etc. and Ord (with appropriate check functions) like: instance Ord Hand where compare (StraightFlush h1) (StraightFlush h2) = compare h1 h2 compare (StraightFlush _) _ = GT compare _ (StraightFlush _) = LT compare (FourOfAKind r1 h1) (FourOfAKind r2 h2)= check r1 h1 r2 h2 compare (FourOfAKind _ _) _ = GT compare _ (FourOfAKind _ _) = LT -- etc Seems like there ought to be an easier way. I can see that making the types of hands an enum (HandType), then defining a hand as a record: data Hand = { type :: HandType, rank1 :: Maybe Rank, -- (2, 3, 4) of a kind rank2 :: Maybe Rank, -- 2 pair, full house cards :: [Card] } would make the comparisons a lot easier. But that would make constructing them a lot more painful. I can't just say "PairOf Ace hand" to mark a hand as a pair of aces. It also the type checking from the constructors. Is there some third alternative I've overlooked that combines the best features of both approaches? Thanks,

Attachments:

attachment.html (text/html — 2.5 KB)

Show replies by date

Daniel Fischer

18 Oct 18 Oct

9:47 p.m.

On Tuesday 18 October 2011, 23:13:03, Mike Meyer wrote:

...

I'm working on a problem dealing with poker hands, and need to rank them. The Ord instance seems like a natural for this, but the code came out with a lot of repetitions in it.

...

Is there some third alternative I've overlooked that combines the best features of both approaches?

Thanks,

Well, you could use record syntax in the Hand type to avoid defining cards in the Eq instance, data Hand = HighCard { cards :: [Card] } | PairOf { rank :: Rank, cards :: [Card } ... | FulHouse { rank, minorRank :: Rank, cards :: [Card] } | FourOfAKind { rank :: Rank, cards :: [Card] } | StraightFlush { cards :: [Card] } deriving Show instance Eq Hand where -- if your hands are well-formed, you h1 == h2 = cards h1 == cards h2 -- could also derive Eq quality :: Hand -> Int quality HighCard{} = 0 quality PairOf{} = 1 ... quality StraightFlush{} = 8 instance Ord Hand where compare h1 h2 = case compare (quality h1) (quality h2) of EQ -> case h1 of StraightFlush c1 -> compare c1 (cards h2) FourOfAKind r1 c1 -> case compare r1 (rank h2) of EQ -> compare c1 (cards h2) other -> other ... other -> other

Mike Meyer

10:27 p.m.

On Tue, Oct 18, 2011 at 2:47 PM, Daniel Fischer < daniel.is.fischer@googlemail.com> wrote:

...

On Tuesday 18 October 2011, 23:13:03, Mike Meyer wrote:

...
I'm working on a problem dealing with poker hands, and need to rank them. The Ord instance seems like a natural for this, but the code came out with a lot of repetitions in it.

...
Is there some third alternative I've overlooked that combines the best features of both approaches?

Thanks,
Well, you could use record syntax in the Hand type to avoid defining cards in the Eq instance,

data Hand = HighCard { cards :: [Card] } | PairOf { rank :: Rank, cards :: [Card } ... | FulHouse { rank, minorRank :: Rank, cards :: [Card] } | FourOfAKind { rank :: Rank, cards :: [Card] } | StraightFlush { cards :: [Card] } deriving Show

instance Eq Hand where -- if your hands are well-formed, you h1 == h2 = cards h1 == cards h2 -- could also derive Eq

I was thinking of some kind of mixed solution over lunch. This looks better than what I had in mind. But what does "well-formed" mean in this context?

...

quality :: Hand -> Int quality HighCard{} = 0 quality PairOf{} = 1 ... quality StraightFlush{} = 8

Could this be replaced by an assoc list of some kind? I was actually contemplating adding a quality field to the record.

...

instance Ord Hand where compare h1 h2 = case compare (quality h1) (quality h2) of EQ -> case h1 of StraightFlush c1 -> compare c1 (cards h2) FourOfAKind r1 c1 -> case compare r1 (rank h2) of EQ -> compare c1 (cards h2) other -> other ... other -> other

What I'd really like to do is collapse the three types of comparison (i.e. - hand, rank hand, rank minorrank hand) into one comparison each. Thanks,

Daniel Fischer

11:01 p.m.

On Wednesday 19 October 2011, 00:27:19, Mike Meyer wrote:

...

On Tue, Oct 18, 2011 at 2:47 PM, Daniel Fischer <

daniel.is.fischer@googlemail.com> wrote:

...
On Tuesday 18 October 2011, 23:13:03, Mike Meyer wrote:

...
I'm working on a problem dealing with poker hands, and need to rank them. The Ord instance seems like a natural for this, but the code came out with a lot of repetitions in it.

Is there some third alternative I've overlooked that combines the best features of both approaches?

Thanks,
Well, you could use record syntax in the Hand type to avoid defining cards in the Eq instance,

data Hand

= HighCard { cards :: [Card] }

| PairOf { rank :: Rank, cards :: [Card }

...

| FulHouse { rank, minorRank :: Rank, cards :: [Card] } | FourOfAKind { rank :: Rank, cards :: [Card] } | StraightFlush { cards :: [Card] } | deriving Show

instance Eq Hand where -- if your hands are well-formed, you

h1 == h2 = cards h1 == cards h2 -- could also derive Eq

I was thinking of some kind of mixed solution over lunch. This looks better than what I had in mind. But what does "well-formed" mean in this context?

That the type of hand is properly reflected in the constructor, that the hand actually has the quality stated by the constructor and no better, for example that a full house is never created as a PairOf or ThreeOfAKind (or was it TripleOf?). And that the list of cards is sorted according to some criterion (this is also presumed in the explicit Eq instance).

...

...
quality :: Hand -> Int quality HighCard{} = 0 quality PairOf{} = 1 ... quality StraightFlush{} = 8

Could this be replaced by an assoc list of some kind?

Sure, but why? Making it an assoc list would not be trivial, if you don't enumerate all possible hands ( ;-), you'd either need a function to create a default hand with the same constructor (so you can use the Eq instance to do the lookup) or some custom lookup function doing basically the same.

...

I was actually contemplating adding a quality field to the record.

If you don't export the constructors and take care to create only hands with the correct quality, that is possible. I'm not sure if it gains anything, though.

...

...
instance Ord Hand where

compare h1 h2 =

case compare (quality h1) (quality h2) of

EQ -> case h1 of

StraightFlush c1 -> compare c1 (cards h2) FourOfAKind r1 c1 ->

case compare r1 (rank h2) of

EQ -> compare c1 (cards h2) other -> other

...

other -> other

What I'd really like to do is collapse the three types of comparison (i.e. - hand, rank hand, rank minorrank hand) into one comparison each.

I don't see what you mean, could you elaborate?

Mike Meyer

11:16 p.m.

On Tue, Oct 18, 2011 at 4:01 PM, Daniel Fischer < daniel.is.fischer@googlemail.com> wrote:

...

On Wednesday 19 October 2011, 00:27:19, Mike Meyer wrote:

...
On Tue, Oct 18, 2011 at 2:47 PM, Daniel Fischer < I was actually contemplating adding a quality field to the record. If you don't export the constructors and take care to create only hands with the correct quality, that is possible. I'm not sure if it gains anything, though.

That's pretty much what playing with it turned up.

...

...
...
instance Ord Hand where

compare h1 h2 =

case compare (quality h1) (quality h2) of

EQ -> case h1 of

StraightFlush c1 -> compare c1 (cards h2) FourOfAKind r1 c1 ->

case compare r1 (rank h2) of

EQ -> compare c1 (cards h2) other -> other

...

other -> other

What I'd really like to do is collapse the three types of comparison (i.e. - hand, rank hand, rank minorrank hand) into one comparison each.

I don't see what you mean, could you elaborate?

The hand types break down into three cases: ordered by the cards in the hand (HighCard, Straight, Flush, StraightFlush) ordered by a rank and then the cards (PairOf, ThreeOfAKind, FourOfAKind) ordered by two ranks and then the cards (TwoPair, FullHouse) I'd like to be able to match against the pattern ignoring the constructor, like so: instance Order Hand where compare h1 h2 = case compare (quality h1) (quality h2) of EQ -> ex_compare h1 h2 ne -> ne where ex_compare (_ c1) (_ c2) = compare c1 c2 ex_compare (_ r1 c1) (_ r2 c2) = case compare r1 r2 of ... ex_compare (_ r1 s1 c1) (_ r2 s2 c2) = case compare r1 r2 of ... Or something similar.

Daniel Fischer

11:36 p.m.

On Wednesday 19 October 2011, 01:16:01, Mike Meyer wrote:

...

On Tue, Oct 18, 2011 at 4:01 PM, Daniel Fischer <

daniel.is.fischer@googlemail.com> wrote:

...
On Wednesday 19 October 2011, 00:27:19, Mike Meyer wrote:

...
On Tue, Oct 18, 2011 at 2:47 PM, Daniel Fischer < I was actually contemplating adding a quality field to the record.

If you don't export the constructors and take care to create only hands with the correct quality, that is possible. I'm not sure if it gains anything, though.

That's pretty much what playing with it turned up.

...
...
...
instance Ord Hand where

compare h1 h2 =

case compare (quality h1) (quality h2) of

EQ -> case h1 of

StraightFlush c1 -> compare c1 (cards h2) FourOfAKind r1 c1 ->

case compare r1 (rank h2) of

EQ -> compare c1 (cards h2) other -> other

...

other -> other

What I'd really like to do is collapse the three types of comparison (i.e. - hand, rank hand, rank minorrank hand) into one comparison each.

I don't see what you mean, could you elaborate?

The hand types break down into three cases: ordered by the cards in the hand (HighCard, Straight, Flush, StraightFlush) ordered by a rank and then the cards (PairOf, ThreeOfAKind, FourOfAKind) ordered by two ranks and then the cards (TwoPair, FullHouse)

I'd like to be able to match against the pattern ignoring the constructor, like so:

That's impossible, pattern matching is against (fully applied) constructors.

...

instance Order Hand where compare h1 h2 = case compare (quality h1) (quality h2) of EQ -> ex_compare h1 h2 ne -> ne where ex_compare (_ c1) (_ c2) = compare c1 c2 ex_compare (_ r1 c1) (_ r2 c2) = case compare r1 r2 of ... ex_compare (_ r1 s1 c1) (_ r2 s2 c2) = case compare r1 r2 of ...

Or something similar.

Guards? ex_compare h1 h2 | plain h1 = compare (cards h1) (cards h2) | oneRank h1 = compare (rank h1, cards h1) (rank h2, cards h2) | otherwise = compare (rank h1, minorRank h1, cards h1) (rank h2, minorRank h2, cards h2) plain HighCard{} = True plain StraightFlush{} = True plain _ = False oneRank FullHouse{} = False oneRank h = not (plain h)

Mike Meyer

19 Oct 19 Oct

12:29 a.m.

Ok, *this* works just fine: data Hand = HighCard {cards :: [Card]} | PairOf {rank1 :: Rank, cards :: [Card]} | TwoPair {rank1, rank2 ::Rank, cards :: [Card]} | ThreeOfAKind {rank1 :: Rank, cards :: [Card]} | Straight {cards :: [Card]} | Flush {cards :: [Card]} | FullHouse {rank1, rank2 :: Rank, cards :: [Card]} | FourOfAKind {rank1 :: Rank, cards :: [Card]} | StraightFlush {cards :: [Card]} deriving (Show, Eq, Ord) The derived order is actually correct - providing, again, that the hands are well-formed (which the unshown constructor makeHand :: [Cards] -> Hand insures). The only writeup I could find for deriving Ord for datatypes was the report. Anyone got a better pointer to one?

5007

Age (days ago)

5008

Last active (days ago)

List overview

Download

6 comments

2 participants

participants (2)

Daniel Fischer
Mike Meyer