A perfect shuffle of a standard deck of 52 playing cards consists of cutting the deck in half (so that the first 26 cards are in one half and the remaining cards are in the other half) and then interleaving the two groups of cards, so that the cards alternately come from the two halves, starting with the first card from the first half. The same principle applies for decks of sizes other than 52, although one detail arises for decks with an odd number of cards: we need a convention for what it means to split the deck in half. We'll assume that the first half gets the extra card, so that in a deck of 5 cards, for example, the first three cards are the first half and the remaining two cards are the other half.
Magicians and group theorists have figured out that eight perfect shuffles restores a deck of 52 cards back to its original configuration. Similar results hold for other sizes of decks, though the magical shuffle number varies with the deck size. In this lab, you will use ML programming in order to explore perfect shuffles.
In order to run the Standard ML system on one of the MCS department
Linux machines, you should use the sml command in a shell
(terminal) window. This should behave approximately as shown in the
textbook. Be sure to ask for help if you need it. The error messages
are often quite inscrutable. One easy thing to try when faced with a
strange error message is to more fully parenthesize your code. Many
beginners run into trouble because ML's default grouping isn't what
they expect. ML is like ordinary math notation, rather than like
Scheme, in that extra parentheses never hurt.
This lab assignment calls on you to write a number of different
function definitions. Although you could in principle type them
directly into the sml system, you would be better off
putting them in a file and loading that file in, as described on
page 83 of the textbook. Also, be sure you pay attention to the
type that the ML system infers for each function. Make sure you
understand what each type means and why it makes sense. You are to
turn in the code you write and the type that was inferred for each
function. For the last problem, you should turn in the expression
that you evaluated and what its value is. Be sure to test each
function as you write it, although you do not need to turn in any
evidence of your testing.
The obvious representation of a deck of cards is as a list.
Later we'll see how the elements of the list can be structured values
that contain suits and ranks (for example, a 3 of hearts). For now,
it will suffice to just use a list of consecutive integers, such as
the list of integers from 1 to 52. That list should be restored to
its original order by 8 perfect shuffles, just as much as a list of
actual cards would be. To produce lists like this, write a function
intsFromTo. It should take a pair of integers,
low and high, and return an list of consecutive
integers in ascending order, namely all those that are greater than or
equal to low and less than or equal to high.
(Under some circumstances, this may be an empty list.)
For use in selecting the first half of a deck of cards (i.e., a
list), define a function, take, that is passed a pair
consisting of a list and the number of elements that should be taken
from the front of the list. For example,
take([10,20,30,40,50],3) would evaluate to
[10,20,30].
For use in selecting the second half of a deck of cards (i.e.,
a list), define a function, drop, that is passed a pair
consisting of a list and the number of elements that should be dropped
from the front of the list. For example,
drop([10,20,30,40,50],3) would evaluate to
[40,50].
The next function you need to define is one to
interleave a pair of lists. For example,
interleave([1,2],[10,20]) would evaluate to
[1,10,2,20].
Now you can put together take, drop,
and interleave in order to write a function called
shuffle that takes a list and returns the result of
performing one perfect shuffle on it. I suggest you read
Section 7.8 if you haven't yet; you will be able to make good use
of a local variable definition. Be sure you get right the case where
the length of the list is odd.
Now write a shuffleNumber function that will take
an integer (the deck size), make a list that size, and return a count
of how many perfect shuffles are needed to return it to a list equal
to the original. You could make good use of a nested function
definition (Section 7.9.)
The approach of testing shuffled lists for equality with the
original is perfectly reasonable. However, for the sake of a really
good example of where pattern matching is helpful, let's consider an
alternative possibility. Given that we start with a list of
increasing integers, we could stop when we return to a list that is
in increasing order. Write a function isInOrder that
takes a list of integers and returns a boolean indicating whether the
list is strictly increasing. Use pattern matching (as described in
Chapter 7) to handle three cases: empty lists, one element lists,
and lists with at least two elements. (You may also want to go back
and look over your earlier function definitions to see if any of them
could be cleaned up a bit using pattern matching.)
Show how to use map to find the shuffle numbers
for 5, 50, 500, and 5000.
The one remaining order of business is to switch to a more realistic representations of the cards, including suit and rank. I'm planning to use that as an in-class example.