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 :: Hand -> Hand -> (Hand,Hand)
If the deck is empty, report an error using error
:
error "draw: The deck is empty."
By changing the type of draw one could get around this rather ugly solution. We will get to that later in the course. Maybe you can think of a way already now?
To return two values a and b in a pair,
use the syntax (a,b).
You can also pattern match on pairs, like in this example:
first :: (a, b) -> a
first (x,y) = x
Given a StdGen
and a hand of cards, shuffle the cards and return the shuffled hand:
shuffle :: StdGen -> Hand -> Hand
A StdGen
is a random number generator.
Import the System.Random
library:
import System.Random
Now, if g is a random number generator, then randomR
(lo,
hi) g is a pair (x,g′), where x is a number between lo and hi (inclusive), and g′ is a new random number generator. Note that to get several random numbers you have to use different random number generators; if you used g this time, then you have to use g′ (or some other generator) the next time. If you were to reuse g then you would get the same result again.
As an example, the following function takes a random number generator as input and uses it to calculate two random integers between 0 and 10, inclusive:
twoRandomIntegers :: StdGen -> (Integer,Integer)
twoRandomIntegers g = (n1, n2)
where (n1, g1) = randomR (0, 10) g
(n2, g2) = randomR (0, 10) g1
Note that if we had used g
in the last line as well, then n1
and n2
would be equal, so instead we use the new random number generator g1
returned by randomR
.
By the way, you can construct a value of type StdGen
by using mkStdGen :: Int -> StdGen
.
So, now that we know how to handle random numbers, how can we shuffle a deck of cards? If you want a (small) challenge, do not read the next three paragraphs.
One way to shuffle the cards would be to pick an arbitrary 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 pick an arbitrary card 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 random number generator is perfect, which it is not).
Note that for both approaches we need a function that removes the n-th card from a deck.
The function shuffle has to satisfy some properties. First, if a card is in a deck before it has been shuffled, then it should be in the deck afterwards as well, and vice versa:
prop_shuffle_sameCards :: StdGen -> Card -> Hand -> Bool
prop_shuffle_sameCards g c h =
c `belongsTo` h == c `belongsTo` shuffle g h
For this we need the helper function belongsTo
, which returns True iff the
card is in the hand.
belongsTo :: Card -> Hand -> Bool
c `belongsTo` Empty = False
c `belongsTo` (Add c′ h) = c == c′ || c `belongsTo` h
(By using `
we can turn a function into an infix operator.)
The above property does not guarantee that the size of the deck is preserved by shuffle; all cards could be duplicated, for instance. You have to write a property which states that the size is preserved:
prop_size_shuffle :: StdGen -> Hand -> Bool