Introduction to Functional Programming

Some notes:

Remember that you have to work in groups of 3. Groups of size 2 can only submit with prior permission. Submissions by only 1 person or more than 3 persons are not allowed.
When you are done, please follow the submission instructions. Important: After the submission deadline you are required to present your solutions as a group to your grader. This will be either on the day of the submission or the day after, depending on your grader. To arrange this you will need to book a presentation slot. This is detailed on the lab overview page and/or the course home page.

Good luck!

About the lab

In this lab assignment, you will write an implementation of (a simple variant of) the game Blackjack.¹ By doing so you will learn how to work with lists using recursive functions and list comprehension. Since you have not really learned how to write programs which interact with the user (so-called input-output), we provide you with a “wrapper” module which takes care of those things for you.

The lab assignment is divided into 2 parts:

Part I: Tasks A to D.
Part II: Tasks E to J.

There are also some extra assignments mentioned after Task J. These are not obligatory, but you will learn more when you do them!

This lab assignment has 3 deadlines (2017):

First deadline (Monday, Sept. 11 at 12:00): Part I as stated above.
Second deadline (Monday, Sept. 18 at 12:00): The whole lab assignment (Parts I and II).
Final deadline (Wednesday, October 11 at 23:59): the system will not accept submissions after this date.

The game

The game you will implement is a simple variant of Blackjack. This section describes the rules that you should implement. We expect your implementation to follow these rules.

There are two players, the “guest” and the bank. First the guest plays. She (he) can draw as many cards as she wants, as long as the total value does not exceed 21. When the guest has decided to stop, or gone bust (score over 21), the bank plays. The bank draws cards until its score is 16 or higher, and then it stops.

The value of a hand (the score) is the sum of the values of the cards. The values are as follows:

Numeric cards have their numeric value, so e.g. a nine is worth nine points.
Jacks, queens and kings are worth ten points each.
Aces are worth either one point or eleven points. When calculating the value for a hand, all aces have the same value; either they are all worth eleven points, or they are all worth one point. Initially the value eleven is used for the aces, but if that leads to a score above 21, then the value one is used instead.

The winner is the player with the highest score that does not exceed 21. If the players end up with the same score, then the bank wins. The bank also wins if both players go bust.

Cards and hands

For this lab, you need the two files Cards.hs and Wrapper.hs. You do not need to understand anything about the wrapper, but you have to understand most of Cards. That module contains some definitions from the lectures; data types and Arbitrary instances for playing cards. See the slides here. Note that in the slides a Hand is defined using a recursive datatype. In this lab we are going to keep things simpler by using a list instead.
Read through the file so that you know which types you are supposed to use.

We will represent a player’s hand as a list of cards ([Card]). For clarity, we defined a type synonym Hand and use it instead of [Card]. We can define an example hand, consisting of the cards 2 of Hearts and Jack of Spades as a list with two elements as follows:

hand2 :: Hand
hand2 = Card (Numeric 2) Hearts : (Card Jack Spades : [])

A more readable way of defining the same hand is:

hand2 :: Hand
hand2 = [Card (Numeric 2) Hearts, Card Jack Spades]

Cards.hs contains a recursive function that computes the number of cards in a hand:

size :: Num a => Hand -> a
size []          = 0
size (card:hand) = 1 + size hand

It is basically the same as the standard function length.

In order to understand how recursion over lists works, take some time to work with it before you continue. You can for instance execute size hand2 by hand, on paper. The result should be 2, right?

Task A. Execute the expression size hand2 by hand, step by step:

size hand2
  = size (Card (Numeric 2) Hearts : (Card Jack Spades : []))
  = ...
  = 2

Write this sequence of equations as a Haskell definition in the following manner:

sizeSteps :: [Int]
sizeSteps = [ size hand2
            , size (Card (Numeric 2) Hearts : (Card Jack Spades : []))
            , ... -- add the remaining steps here
            , 2
            ]

sizeSteps should just compute a list containing several copies of the number 2 (so using this definition you can check your steps).

Put this and all the assignments of this lab in a file called Blackjack.hs. This is the file you will submit.

Properties

To help you we have included a couple of QuickCheck properties below. Your functions must satisfy these properties. If they do not, then you know that something is wrong. Testing helps you find bugs that you might otherwise have missed. Note that you also have to write some properties yourself, as indicated below.

The purpose of writing properties is three-fold:

They serve as a specification before you write your functions.
During the implementation phase they help you with debugging.
When you are finished they serve as mathematically precise documentation for your program.

So, to take maximum advantage of the properties, write them before you write the corresponding functions, or at the same time.

Documentation

The code has to be documented. See the Cards.hs and Wrapper.hs modules to get an idea about what kind of documentation is expected of you. Try to follow these guidelines:

Focus on what the function does and how one can use it, but not on how the function is implemented. Of course, if a function is complicated then the implementation also has to be documented, but you are not supposed to write complicated functions in this assignment.
Try to keep the documentation as short as possible, without sacrificing clarity. Long comments make the code harder to read.

Similar arguments apply to documentation as for properties; write the documentation when you write your functions, not afterwards.

Functions

Write all code in a file called Blackjack.hs. To make everything work, add the following lines at the top of the file:

module Blackjack where

import Cards
import Wrapper

This tells the Haskell system that the module is called Blackjack, and that you want to use the functions and data types defined in Cards and Wrapper. Download Cards.hs and Wrapper.hs and store them in the same directory as Blackjack.hs, but do not modify those files.

As usual, when using QuickCheck you need to first import it. However, it turns out that recent versions of QuickCheck define a function shuffle whose name clashes with the function you are supposed to define in task H. To avoid this problem, you can import QuickCheck as follows:

import Test.QuickCheck hiding (shuffle)

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. If it cannot find QuickCheck then you probably installed the minimal version of the Haskell platform which comes without without QuickCheck. Install the full version instead, or if bandwidth is an issue, type cabal install QuickCheck in a command window.

When working on the functions below, it is a good idea to make two definitions,

aCard1 :: Card
aCard1 = ... -- define your favorite card here

aCard2 :: Card
aCard2 = ... -- define another card here

so that you can use these cards to test your functions. Also, make a definition,

aHand :: Hand
aHand = ... -- a Hand with two Cards, aCard1 and aCard2

to test your functions that work on hands.

Task B. Implement a function that, given a hand, shows the cards in it in a nice format.

display :: Hand -> String

For example, display can show the card Card (Numeric 2) Hearts as "2 of Hearts", and the card Card Jack Spades as "Jack of Spades". If you want to show the card suits as pictures instead, use Unicode characters, \9829 for Hearts, \9824 for Spades, \9830 for Diamonds, and \9827 for Clubs. To display the hand over several lines you might want to use the unlines function.

Hint: Start by writing a function displayCard :: Card -> String that shows a single card as a building block.

Try out your function using putStr (display aHand).

Task C. Implement a function that, given a hand, calculates the value of the hand according to the rules given above.

value :: Hand -> Int

Remember that the special rules for this lab state that all aces have the same value: they are either all 1 or all 11 depending on the total value of the hand.

Hint: To write the value function, start by writing a function valueRank :: Rank -> Int, that calculates the value of a Rank (think about what to do for an ace!), and perhaps also a function valueCard :: Card -> Int, that calculates the value of a Card. Furthermore, it is a good idea to define and use a function numberOfAces :: Hand -> Int, that calculates the number of aces in a given hand. Write these three functions first before you start defining the function value.

Task D. Implement two more functions that are necessary in the game.

Implement a function that, given a hand, checks if the player is bust.
```
gameOver :: Hand -> Bool
```
Implement a function that, given one hand for the guest and one for the bank (in that order), checks which player has won.
```
winner :: Hand -> Hand -> Player
```
Here Player is a new data type, defined in Wrapper.hs:
```
data Player = Guest | Bank
              deriving (Show, Eq)
```

The remaining tasks belong to Part II of the lab.

In this part we will need to represent a deck of cards (the cards from which the hand is dealt). We could also represent the deck of cards as a list of cards, but if we do this it is easy to mix up a deck of cards with a hand. To prevent this kind of error we have introduced a new data type for a Deck.

Task E. 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. Remember that to turn a list of cards into a Deck you need to apply the constructor function Deck.

Your fullDeck function must satisfy the following property:

prop_size_fullDeck :: Bool
prop_size_fullDeck = size (cards fullDeck) == 52

Task F. 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."

Hint: To return two values a and b as a pair, use the syntax (a, b). This syntax is also used for pattern matching on pairs:

first :: (a, b) -> a
first (x, y) = x

Task G. Given a deck, play for the bank according to the rules above (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 here.

Task H. 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

Note: See above about how to import QuickCheck without getting name clashes with the shuffle function.

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.

Hint (Simpler coding) As a practical hint, you will find it easier to define a helper function shuffle' :: [Double] -> [Card] -> [Card] to do the main work, and then use this to define shuffle.

Task I.

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.

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` (Deck [])      = False
c `belongsTo` (Deck (c':cs)) = c == c' || c `belongsTo` (Deck 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 to define a new type:
```
data Rand = Rand [Double]
```
We have done this for you, and more importantly, for this new type we have told quickCheck how to generate infinite lists of the right kind! So now we can check the property defined 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.
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 cardlist) = undefined
```

Interface

You have barely touched upon input/output in the lectures, so we have to provide you with a wrapper that takes care of those things. All you have to do is to write the functions above, package them together (as explained below), and then call the wrapper with the package as an argument.

Task J. 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.

Best of luck!

Possible extensions

The following is completely optional, but if you want to do more, there are many possibilities:

Now the bank draws all its cards after the guest has finished. It would be more fun if the guest could see the bank’s cards while playing.
The rules are not really proper Black Jack rules.
There are many other card games, many of which may be more fun than this one.
You probably have some ideas yourself.

Most of the ideas above require that you program input/output (I/O) yourself. You have seen how to do simple I/O in the lectures. Use the Wrapper.hs module as a starting point.

Note that doing something extra will not directly affect your grade, but can of course be beneficial in the long run. Take care to do the compulsory part above before attempting something more advanced, though.

Submission

Write your answers/solutions in one file, called Blackjack.hs. For each assignment, use Haskell comments to indicate what part of the file contains the answer to the assignment. For answers in natural language, you can use Swedish or English; write these answers also as Haskell comments.

Before you submit your code, clean it up! Remember, submitting clean code is Really Important, and simply the polite thing to do. After you feel you are done, spend some time on cleaning your code; make it simpler, remove unneccessary things, etc. We will reject your solution if it is not clean. Clean code:

Does not have long lines (< 78 characters)
Has a consistent layout (do not use TAB characters in your code)
Has type signatures for all top-level functions
Has good comments
Has no junk (junk is unused code, commented code, unneccessary comments)
Has no overly complicated function definitions
Does not contain any repetitive code (copy-and-paste programming)

Please do not submit the modules Cards.hs and Wrapper.hs (unless an extra assignment required you to make changes to them).

When you are done, please submit it using the Fire system.

Once you have submitted, please arrange to present your solution to one of the course assistants according to the instructions on the lab overview page.

Good luck!

This lab is based on material by Nils Anders Danielsson, Koen Claessen, Hampus Ram, Andreas Farre, Sebastian Sylvan and Mary Bergman.↩

Introduction to Functional Programming – Lab 2: “Blackjack”	TDA555 / DIT440, LP1 2017
Home \| Schedule \| Labs \| Lectures \| Exercises \| Exam \| About \| FAQ	Fire \| WaitList \| Group \| TimeEdit \| YouTube \| Links

Introduction to Functional Programming – Lab 2: “Blackjack”	TDA555 / DIT440, LP1 2017
Home \| Schedule \| Labs \| Lectures \| Exercises \| Exam \| About \| FAQ	Fire \| WaitList \| Group \| TimeEdit \| YouTube \| Links