Lab: Blackjack - part B

If you get an error about shuffle here it probably means you have an older version of QuickCheck, in which case just comment out the hiding (shuffle) part.

Task B1

You also need to define a function that returns a full deck of cards:

fullDeck :: Deck

You could do this by listing all 52 cards, like we did with two cards above. However, that is very tedious. Instead, do it like this: Write a function that returns a list of all possible ranks, and a function that returns given all possible suits, and then combine their results.

Your fullDeck function must satisfy the following property:

prop_size_fullDeck :: Bool
prop_size_fullDeck = size fullDeck == 52

Task B2

Given a deck and a hand, draw one card from the deck and put on the hand. Return both the deck and the hand (in that order):

draw :: Deck -> Hand -> (Deck, Hand)

If the deck is empty, report an error using error:

error "draw: The deck is empty."

Task B3

Given a deck, play for the bank according to the rules mentioned in the previous assignment (starting with an empty hand), and return the bank’s final hand:

playBank :: Deck -> Hand

To write this function you will probably need to introduce a helper function that takes the deck and the bank’s hand as input. To draw a card from the deck you can use where in the following way:

playBank' deck bankHand  ...
                         ...
  where (deck', bankHand') = draw deck bankHand

You can read more about where in the FAQ.

Task B4

This is the hardest part of the lab. Write a function that shuffles a hand deck of cards. The function shuffle should take a deck of cards and return a deck with all the cards placed in random order.

Since Haskell functions are functions in the mathematical sense, they always give the same result if you give them the same argument. This means it is impossible to write a Haskell function that takes a deck of cards and returns a randomly shuffled deck!

The way we will sidestep this problem is to define a function which takes two arguments, the deck to be shuffled (as second argument) and a parameter representing the “randomness” as an input.

To understand how this will work, imagine that you want to take a random walk in a maze. Do this you are given really big stack of coins which have been randomly flipped and piled in a stack. Whenver you have to make a choice between going left or right you look at the coin at the top of the stack: heads (krona) and you go left, tails (klave) and you go right. But to make your walk random you must discard the top coin after you have used it. Assume that the stack is big enough that you never run out. Your path is a function of the coin stack that you had as input.

You will implement a shuffle function is a similar manner. Instead of a stack of coins you will have a list of floating point numbers (type Double) in the range 0 to 1. You may assume that this list is big enough that you will never run out of random numbers to use, no matter how long you shuffle. For your convenience, Cards.hs will generate lists of floating point numbers from 0 to 1 to give it to the shuffle function as the first argument. (To make quickCheck able to do its work, we limit the list to 52 numbers, so don’t over-shuffle!).

Define the function:

shuffle :: [Double] -> Deck -> Deck

Optional Task 4.1

If you want a (small) challenge, try to implement shuffle without reading the following hints. Hint (Shuffling strategy): One way to shuffle the cards would be to pick an random card from the deck and put it on top of the deck, and then repeat that many times. However, how many times should one repeat? If one repeats 52 times, then the probability that the last card is never picked is about 36%. This means that the last card is often the same, which of course is not good.

A better idea is to randomly pick a card from the deck and put it in a new deck, then pick another card and put it on top of the new deck, and so on. Then we know that we have a perfectly shuffled deck in 52 steps (given that the input list of numbers is perfectly random, which it is not). Remember of course that to "pick a random card" we will use the list of random values that shuffle gets as its first argument.

Note that for both approaches we need a function that removes the n-th card from a deck.

Task B5

The function shuffle has to satisfy some properties. In this task we give an example of one useful property, and you are required to define a second property of the shuffle function.

1. If a card is in a deck before it has been shuffled, then it should be in the deck afterwards as well. To write that as a property we need the helper function belongsTo, which returns True if and only if the card is in the hand.

   belongsTo :: Card -> Deck -> Bool
   c `belongsTo` []      = False
   c `belongsTo` (c':cs) = c == c' || c `belongsTo` cs

   (Here we’re using ` to turn a function into an infix operator just to make the code more natural to read.)

   With this helper function we can now define the property that shuffling does not change the cards in a hand as:

   card `belongsTo` deck == card `belongsTo` shuffle randomlist deck

   But if we define a quickCheck property using this it will fail because quickCheck does not know that the list randomlist that we need for testing should be an infinite list of values between zero and one, and not just any old list of doubles. The way we get around this is that we have defined a new type in Cards.hs:

   data Rand = Rand [Double]

   More importantly, for this new type we have told quickCheck how to generate infinite lists of the right kind! (Note: the actual type of Rand is more complicated than this, but you should think of this definition when you use it).

   We define the shuffle property as follows:

   prop_shuffle :: Card -> Deck -> Rand -> Bool
   prop_shuffle card deck (Rand randomlist) =
       card `belongsTo` deck == card `belongsTo` shuffle randomlist deck

   This is the first property you should use to test your shuffle function.

2. But this property still allows for errors. For example the above property would hold even if the shuffle function added duplicate cards to the deck.

   The second property, the one you must define in this task, is a property to check that the size of the deck does not change when you shuffle.
   This would allow you to check that you don’t accidentally duplicate cards. Complete the following definition:

   prop_size_shuffle :: Rand -> Deck -> Bool
   prop_size_shuffle (Rand randomlist) deck = undefined

   Now run quickCheck on your properties to actually check that they actually hold!

Task B6

To “package up” these functions, write the following code:

implementation = Interface
  {  iFullDeck  = fullDeck
  ,  iValue     = value
  ,  iDisplay   = display
  ,  iGameOver  = gameOver
  ,  iWinner    = winner
  ,  iDraw      = draw
  ,  iPlayBank  = playBank
  ,  iShuffle   = shuffle
  }

(Note that Interface is just an ordinary data type, here constructed using record syntax.)

To run the program, define

main :: IO ()
main = runGame implementation

in your source file, load the file in GHCi, and run main.