CS470/570 Problem Set 2: Recursive Data Structures

Revision History
Sep 23	Q2: Added case class DEmpty to DBinaryTree

Due: September 23, 2016

---

How and What to Submit:

Homework for all problem sets will be submitted using the Canvas Assignments tool. Most homeworks will consist mainly of Scala files. For each assignment, you get to submit some text and some attachments. For many assignments, including this one, there will be no text (or just some pro forma line such as "Here is my homework for PS2"). There will be several attachments, consisting of Scala files, class files, text files, and runs of your program. For this assignment, attach the files PS2Q1.scala, DBinaryTree.scala, and TreeList.scala. At the end of PS2Q1.scala and TreeList.scala, append a comment with the output from PS2Q1Demo and TreeListDemo

As spelled out at length in the lecture notes for lecture 2 the file Resources > Scripts contain some helpful shell scripts for compiling and running Scala programs. The Scala compiler usually generates more class files than the Java compiler for a program of similar size. To hide this clutter away, create a bin directory below the directory your code appears in, then use the shell scripts scc and sca instead of scalac and scala. (These scripts work in any Unix system, including OS X and Linux. Windows users should choose scc.bat and sca.bat instead.)

1 Create a file PS2Q1.scala. This is where the answers to this problem will go. It should start out looking like this schematic:

class PS2Q1(nl: List[Int]) {
  val nums: List[Int] = nl

  /** The nonnegative elements of nl
    */
  def nonNegs: ...

  /** Return a list of Booleans the same length as nums, true for element
    * I if it's == to element I+1.  (If there is no element I+1, i.e, if
    * we're at the end of the list, the Boolean value is 'false'.)
    */
  def doubledElts: ...

  /** Return a list of elements K such that there are K elements
    * _after_ it.  Example: If nums  = List(1, 2, 3, 4), the value of
    * 'tailsThatLength' is List(2).
    */
  def tailsThatLength: ...

  override def toString: String = "PS2Q1(" + nums.mkString(", ") + ")"
}

object PS2Q1Demo extends App {
   ...
}

1A Define the methods nonNegs, doubledElts, and tailsThatLength, whose definitions are given in the comments just before them.

1B Define the body of the object PS2Q1Demo so that when run (using sca PS2Q1Demo) its output will start thus:

v1 = PS2Q1(1, -2, -2, 3, 4, 4, -4, 3, 5)
v1.nonNegs = List(1, 3, 4, 4, 3, 5)
v1.doubledElts = List(false, true, false, false, true, false, false, false, false)
v1.tailsThatLength = List(4)

v2 = PS2Q1(2, 2, 2, 3, 4, 5, 6)
v2.nonNegs = List(2, 2, 2, 3, 4, 5, 6)
v2.doubledElts = List(true, true, false, false, false, false, false)
v2.tailsThatLength = List(3)

v3 = PS2Q1(5, 4, 3, 2, 1, 0)
v3.nonNegs = List(5, 4, 3, 2, 1, 0)
v3.doubledElts = List(false, false, false, false, false, false)
v3.tailsThatLength = List(5, 4, 3, 2, 1, 0)

v4 = PS2Q1()
v4.nonNegs = List()
v4.doubledElts = List()
v4.tailsThatLength = List()

...

You can add further examples of your own, but these are essential. Remember that when we give specifications for the output to be produced, you are to produce that output, not something of your own devising, no matter how much more clever to read or convenient to write.

You can compile PS2Q1.scala and put all of the resulting class files in your bin subdirectory by executing

$ scc PS2Q1.scala

Once the compiler is happy, run the program by executing

$ sca PS2Q1

If you're using an IDE, the procedure will differ.

2 In Lecture Note 5^{Lecture Note} the trait DBinaryTree is defined, with one method, findNearestLeaf. (A better place to download the code for DBinaryTree is here; or find it on Canvas under Files > Code > Problem-set Software, with the name DBinaryTree-without-addKeyVal.scala.)

Add a method addKeyVal whose definition starts:

  def addKeyVal(p: Double, val: A): DBinaryTree[A] = {

It must have the following two properties: If T is a sorted DBinaryTree, then T' = T.addKeyVal(p, v) is sorted as well; and contains the same assocations plus (p,v), except for an old association (p,v'), if any, which should not be present in T′.

In the preceding paragraph, we used the terms "sorted" and "associations," which we now define. The associations of a DBinaryTree D are all the (k,v) pairs at or below D.

A DBinaryTree is sorted if at every interior node (DIntNode(l,n,r)), every key number of l is <n and every key numbers of r is ≥n. The key numbers of a DBinaryTree D are all the keys and nums of D and its subtrees.

3 In this problem we're going to define and work with tree-lists, which are recursive tree structures whose leaves are lists of data of some kind. The interior nodes are lists of tree-lists.

The overall datatype (hint: a trait) should be called TreeList[A], where A is the type of data in the bottom lists of the tree. It has two case classes, one called TreeListLeaf, whose consructor takes one parameter, data, a list of As; and one called TreeListNode, whose constructor takes are parameter, subLists a list of subtrees. To be as explicit as possible, subLists is of type List[TreeList[A]]. (We are being coy about who binds A here.)

An example of a TreeList is the object built thus:

  TreeListNode[Int](List(TreeListLeaf(List(3, 2, 1)),
                         TreeListNode(List()),
                         TreeListNode(List(TreeListLeaf(List(1)),
                                           TreeListLeaf(List()),
                                           TreeListLeaf(List(2, 1)))))

3A In the companion object for PS3, define a function sum that takes a TreeList[Int] and returns the sum of all the numbers contained in it. It goes without saying tht treeList.sum should be recursive and use pattern matching. Explain in a comment why sum should be defined in the companion object and not in the class. (I.e., why should we write TreeList.sum(t) instead of t.sum?)

3B In the class TreeList define a method flatten that returns a list of all the objects in all the lists at the leaves of this. Explain in a comment why it's possible and more natural to define flatten in the class and not in the companion object. That is, why are we able to write t.flatten instead of TreeList.flatten(t)?

3C After that little warm-up, this one is a bit trickier: to write a toString method for TreeLists. To avoid clutter, we'd like the string to show only the bracket structure of the sublists for sublists. (And it will use square brackets to emphasize the artificiality.) So the example object above should print thus:

TreeList[[3, 2, 1], [], [[1], [], [2, 1]]]

The file TreeList-without-answers.scala contains the definitions of TreeList, the headers of the three desired procedures (sum, flatten, and toString), and the definition of TreeListDemo, an object that runs the various functions on various TreeLists. Download this file, fill in the missing pieces, and verify that the result compiles and runs.