MCS-287 Lab 1 (Spring 2009)

Due March 6, 2009

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.

  1. 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.)

  2. 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].

  3. 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].

  4. 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]. The first list may have one more element in it than the second list does; be sure your procedure works in this case as well.

  5. 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.

  6. 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.) Test that the shuffle number for 52 is 8.

  7. 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.)

  8. Show how to use map to produce a list of 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.