in Haskell

Part 3 Lists

Total: 45 Points

Problem 4 [45 Points]. The following set of problems is about shuffling of cards, particularly something called the Faro shuffle, where the stack is broken up into two, and then combined so that a card from one sub-stack is followed by one from the other, and so on. A perfect Faro shuffle breaks up the stack into two sub-stacks of exactly the same size, and then combines them in the manner described above. An out-shuffle results in the top and the bottom cards of the stack remaining the same after the shuffle; an in-shuffle results in these cards becoming the second and the second last cards of the shuffled stack.

(a) [10 Points]. Write a polymorphic function, shuffle, which takes two lists l1 and l2 representing decks of cards, and returns the result of a combining of the lists. Particularly, the returned list contains the first element of l1, followed by the first element of l2, followed by the second element of l1, and so on. If one of the lists ends before the other, the other lists remaining elements are simply added to the end.

(b) [7 Points]. Write a polymorphic function, split, which takes as parameters a list and an integer n, indicating the splitting point. It splits the contents of the provided list into two lists, the first with the first n elements of the list (in order), and the second with the remaining elements (again, in order). These two lists are then returned as a list of two lists.

(c) [8 Points]. Write two polymorphic functions outshuffle and inshuffle, which use shuffle and split functions described above (and possibly additional intermediary functions), and carry out perfect Faro shuffles of the out-shuffle and in-shuffle type. In other words, they take a single stack of an even number of cards, break them up and return the result of applying the required type of Faro shuffle exactly once.

(d) [10 Points]. Write a polymorphic function, nshuffle, which takes three parameters, a shuffle function (such as outshuffle or inshuffle), an integer indicating how many shuffles to carry out, and a list to shuffle, which is of even length. It then carries out the required number of shuffles on the list, and returns the result.

(e) [10 Points]. Write a function howManyShuffles, which takes three parameters: a shuffle function (such as outshuffle or inshuffle), and two lists of even size. It repeatedly applies the provided shuffle function on the first of the two lists, until it becomes identical to the second list, and returns the count of the number of shuffles that were required.

As part of your testing of howManyShuffles, find out:

a) How many out-shuffles are required to return a stack of 52 cards to its original ordering?

b) How many in-shuffles are required to completely reverse a stack of 52 cards?