Haskell instance function

Question

I'm solving some exercises from a book and now I'm having some difficulties: In this exercise I shall implement Card as an instance of the class Ord. But I don't know how exactly I could implement it, so I would appreciate any help.

My code so far looks like this:

data Suit = Diamond | Club | Spade | Heart

data Rank = Seven | Eight | Nine | Ten | Jack | Queen | King | Ace

data Card = Card Suit Rank

instance Ord Card where
 .... 

Now I don't know how exactly to implement this and I would very much like to understand it. Thanks in advance for the explanations.

Answer 1

I can't imagine the exercise actually wanted you to manually write the necessary instances. Especially for Suit and Rank, they would be very tedious (and error prone) to write.

Instead, you probably want to use the deriving keyword to automatically derive the necessary instances. If you write:

data Suit = Diamond | Heart | Spade | Club
  deriving (Eq, Ord)

this automatically derives Eq and Ord instances. (The Eq instance is required by the Ord instance.) The derived Eq instance is self-explanatory, and the derived Ord instance uses the order in which the constructors appear in the declaration, so Diamond is the smallest and Club is the biggest. If you want bridge order, use:

data Suit = Club | Diamond | Heart | Spade
  deriving (Eq, Ord)

instead. Similarly,

data Rank = Seven | Eight | Nine | Ten | Jack | Queen | King | Ace
  deriving (Eq, Ord)

orders the rank from Seven (smallest) to Ace (largest). Then, if you write:

data Card = Card Rank Suit
  deriving (Eq, Ord)

the derived instance sorts Cards according to the first field Rank, with ties broken by Suit. If you wrote:

data Card = Card Suit Rank
  deriving (Eq, Ord)

it would instead order them by Suit, then Rank.

Some code to illustrate:

data Suit = Diamond | Heart | Spade | Club
  deriving (Eq, Ord)

data Rank = Seven | Eight | Nine | Ten | Jack | Queen | King | Ace
  deriving (Eq, Ord)

data Card = Card Rank Suit
  deriving (Eq, Ord)

main = do
  let heart8 = Card Eight Heart
      spade8 = Card Eight Spade
      diamond7 = Card Seven Diamond

  print $ heart8 == heart8   -- True
  print $ heart8 == spade8   -- False
  print $ heart8 < spade8    -- True
  print $ diamond7 < spade8  -- True

Answer 2

We can ask GHCi for information about Ord.

:info Ord

This shows the class definition, followed by a list of instances.

type Ord :: * -> Constraint
class Eq a => Ord a where
  compare :: a -> a -> Ordering
  (<) :: a -> a -> Bool
  (<=) :: a -> a -> Bool
  (>) :: a -> a -> Bool
  (>=) :: a -> a -> Bool
  max :: a -> a -> a
  min :: a -> a -> a
  {-# MINIMAL compare | (<=) #-}
    -- Defined in ‘GHC.Classes’

Its superclass is Eq, and :info Eq tells us:

type Eq :: * -> Constraint
class Eq a where
  (==) :: a -> a -> Bool
  (/=) :: a -> a -> Bool
  {-# MINIMAL (==) | (/=) #-}
    -- Defined in ‘GHC.Classes’

So in order to implement Ord for Card, we need two things:

• An instance Ord Card, with a definition of compare or (<=)
• An instance Eq Card with a definition of (==) or (/=)

Since these instances are very mechanical to write, normally we ask the compiler to derive them automatically:

data Suit = Diamond | Heart | Spade | Club
  deriving (Eq, Ord)

data Rank = Seven | Eight | Nine | Ten | Jack | Queen | King | Ace
  deriving (Eq, Ord)

data Card = Card Suit Rank
  deriving (Eq, Ord)

If you pass the -ddump-deriv flag to GHC, or use :set -ddump-deriv in GHCi, it will print out the code that it generates for these instances.

However, the task is to understand how to implement these instances by hand, so let’s go through it step by step.

We’ll start with Eq. For Suit and Rank, we need to specify that each constructor is equal to itself (a.k.a. reflexivity) and all other constructors are unequal.

instance Eq Suit where
  Diamond == Diamond  = True
  Heart   == Heart    = True
  Spade   == Spade    = True
  Club    == Club     = True
  _       == _        = False

instance Eq Rank where
  Seven == Seven  = True
  Eight == Eight  = True
  Nine  == Nine   = True
  Ten   == Ten    = True
  Jack  == Jack   = True
  Queen == Queen  = True
  King  == King   = True
  Ace   == Ace    = True
  _     == _      = False

With that out of the way, we can define == for Card in a similar way, by pattern-matching on values of the form Card suit rank.

instance Eq Card where

  -- Two cards are equal if…
  Card suit1 rank1 == Card suit2 rank2

    -- …their suits are equal,
    -- and their ranks are equal.
    = …

There are two conventional ways to define the body. One is spelling it out literally: suit1 == suit2 && rank1 == rank2. Another is to use tuples: (suit1, rank1) == (suit2, rank2).

Again, to define Ord, we can begin with the instances for the enumerations Suit and Rank. We have two choices of how to specify these: (<=) or compare. The direct option is to just list out the table of possible cases, abbreviating cases where we can:

instance Ord Suit where

  Diamond <= _        = True

  Heart   <= Diamond  = False
  Heart   <= _        = True

  Spade   <= Diamond  = False
  Spade   <= Heart    = False
  Spade   <= _        = True

  Club    <= Club     = True
  Club    <= _        = False

instance Ord Rank where

  …

For Card, we now just need to follow the same basic form as for Eq. Since we defined (<=) for Suit and Rank, note that we automatically get a default implementation of the other comparison functions like compare and (<) for those types.

instance Ord Card where

  -- Two cards are in order if…
  Card suit1 rank1 <= Card suit2 rank2
    -- …one rank is less than the other,
    -- or their ranks are equal and suits are in order.
    = …

Again you can translate this comment verbatim using (<), (||), (==), (&&), (<=).

Try implementing these instances based on compare instead of (<=). Hint: use comparing and instance Monoid Ordering from Data.Ord.

Add deriving (Enum) to Rank and Suit—try using fromEnum to simplify their Eq and Ord definitions.