Haskell Cyclic Ord Relationship

user_1079328 0
Viewed 256

I was trying to define a data type for rock paper scissors and came up with something like this: 

data Hand = P | S | R deriving (Show, Eq)

instance Ord Hand where
  compare R P = LT
  compare P R = GT
  compare R S = GT
  compare S R = LT
  compare P S = LT
  compare S P = GT
  compare _ _ = EQ

While writing all that I was wondering if there's any way to define the data type to just have it derive Ord and then specify that compare R P = LT and compare P R = GT instead of having to write all the comparisons by hand, for three elements it's okay but it would get tedious with each added element.

algebraic-data-types haskell
3 Answers

What you describe here is not an order relation. An order relation is:

  1. reflexive, all values x are less than or equal tot itself;
  2. antisymmetric: if x is less than or equal to y and y is less than or equal to x, then x is equal to y;
  3. transitive: if x is less than or equal to y, and y is less than or equal to z, then x is less than or equal to z.

Your definition is not transitive. Indeed: S is less than R, R is less than P, but S is not less than P. I therefore would strongly advice you not to use Ord, since for instance sorting, etc. make use of these invariants.

What you can do is let it derive from Ord automatically:

data Hand = P | S | R deriving (Show, Eq, Ord)

and then define a function beats:

beats :: Hand -> Hand -> Ordering
beats R P = LT
beats P R = GT
beats x y = compare x y
user_675790

You can write generic variant of this function:

cyclicRelation :: (Bounded a, Ord a) => a -> a -> Ordering
cyclicRelation x y | x == minBound && y == maxBound = GT
                   | x == maxBound && y == minBound = LT
                   | otherwise                      = x `compare` y

Then just derive needed instances:

data Hand = P | S | R deriving (Show, Eq, Ord, Bounded)
user_71751170

I liked @freestyle's answer best and influencing by that just draw a Cirord type class which may be applicable to any such cyclic ordered data type like Pokemons etc :)

class (Bounded a, Ord a) => Cirord a where
  ccompare   :: a -> a -> Ordering
  cmax, cmin :: a -> a -> a

  ccompare x y = let mima = [minBound, maxBound]
                 in if x `elem` mima && y `elem` mima then compare y x
                                                      else compare x y

  cmax x y = if ccompare x y == LT then y else x
  cmin x y = if ccompare x y == LT then x else y

data Hand = P | S | R deriving (Show, Eq, Ord, Bounded)
instance Cirord Hand

*Main> ccompare P R
GT
*Main> ccompare S R
LT
*Main> ccompare R S
GT
*Main> ccompare R P
LT
*Main> ccompare P S
LT
*Main> ccompare S P
GT
user_45432070
Related