Scala Programming Question

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