Programming Language: Scala

[Do not use built-in higher order functions, for comprehension, or any other advanced features of Scala not covered in class prior to release of the assignment. You must provide signature for every function, including the return type. Whenever meaningful, use type variables instead of types. Finally, ensure that the parameters passed to the functions are of the correct types and are passed in the correct order.]

Problem 1 [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.

[Note: Do not use built-in higher-order functions for this problem]

(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 polymorphic function, howManyShuffles, which takes three parameters: a shuffle function (such as outshuffle or inshuffle), and two lists of even size. It keeps applying the 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, try to 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?

Problem 2 [35 Points]. Define a polymorphic Tree data type, where a Tree is either a Node with a left subtree, a value, and a right subtree; or it is Null. Also define a companion object for the Tree data type, with the following functions:

(a) [15 Points]. Three polymorphic functions -- inOrder, preOrder, and postOrder -- to traverse the tree in-order, pre-order, and post-order. Each function takes a tree and returns a list with the contents of the tree when traversed in that order.

(b) [5 Points]. A polymorphic function, search, which takes two arguments a Tree and a key and returns a boolean result based on whether the key is found in the tree.

(c) [5 Points]. A polymorphic function, replace, which takes three arguments a Tree t, a value before, and a value after and returns t with ALL instances of before replaced with the value after.

[Hint: Model your Tree data type after the List data type presented in class.]

Problem 3 [20 Points]. A higher-order function unfold can be defined as follows to encapsulate a pattern of recursion for producing a list:

def unfold[A, B] (p: A => Boolean,

h: A => B,

t: A => A)

(x: A) : List[B] =

if (p(x))

Nil

else

h(x) :: unfold(p, h, t) (t(x))

That is, the function call unfold(p, h, t, x) produces the empty list if the predicate p is true of x, and otherwise produces a non-empty list by applying the function h to x to give the head, and the function t to x to generate another argument that is recursively processed in the same way to produce the tail of the list.

Define the following functions using unfold:

(a) [10 Points]. A function, int2bin, to convert integers to binary numbers.

[Hint: Repeatedly dividing the integer by 2 can give values of bits for the binary number]

(b) [10 Points]. A function, repHalve, where repHalve takes list l, and returns a list of lists containing the elements of l, so that the first list contains half of ls elements, the next contains half of the remaining elements, and so on. For example, repHalve (List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15)) should return:

List(List(1, 2, 3, 4, 5, 6, 7, 8), List(9, 10, 11, 12), List(13, 14), List(15))