CS470/570 Problem Set 2 (PS2): Solutions

1 Here is one way to complete PS2Q1.scala:

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

  /** The nonnegative elements of nl
    */
  def nonNegs: List[Int] = nums.filter(_ >= 0)

  /** 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: List[Boolean] = nums match {
    case Nil => Nil
    case _ :: t => (nums zip t).map({case (x,y) => x == y}) ::: List(false)
  }

  /** 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: List[Int] = {
    // tailPairs is a list of pairs (K, T), such that K is contained
    // in `nums` and T is the tail
    // of `nums` starting with K. The `filter` operation ensures that
    // T is indeed of length K –
    // So K is one of the numbers we seek –
    val tailPairs: (Int, List[Int]) = 
      (nums zip nums.tails.toList).filter({
        case (num, tail) => num == tail.length - 1
      }) 
    // Now just pluck out the Ks –
    tailPairs.map({
      case (num, _) => num
    })
  }

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

object PS2Q1Demo extends App {

  private def demo(name: String, x: PS2Q1): Unit = {
    println(name + " = " + x)
    println(name + ".nonNegs = " + x.nonNegs)
    println(name + ".doubledElts = " + x.doubledElts)
    println(name + ".tailsThatLength = " + x.tailsThatLength)
    println()
  }

  private def buildPS2Q1(elements: Int*): PS2Q1 = new PS2Q1(elements.toList)

  val v1: PS2Q1 = buildPS2Q1(1, -2, -2, 3, 4, 4, -4, 3, 5)
  demo("v1", v1)
  val v2: PS2Q1 = buildPS2Q1(2, 2, 2, 3, 4, 5, 6)
  demo("v2", v2)
  val v3: PS2Q1 = buildPS2Q1(5, 4, 3, 2, 1, 0)
  demo("v3", v3)
  val v4: PS2Q1 = buildPS2Q1()
  demo("v4", v4)
}

Another way to derive the value of tailPairs in tailsThatLength (question 1C) is

      (nums zip nums.tails.tail.toList).filter({
        case (num, tail) => num == tail.length
      }) 

By taking the tail of nums.tails, we discard the first tail, so each element of nums is paired with a tail shorter by 1. Why don't we run out of tails? Because a list of N elements has N+1 tails, one per position in the list. The empty list, for instance yields List().tails = List(List()), a list with 1 element. If we take its tail, we get List(), which yields an empty tailPairs, as it should.

Addendum after writing the rubric: It came to me that tailsThatLength (either version above) was quite wasteful. I violated my own rule about calling length repeatedly! We really need to call it just once, and use subtraction instead of repeatedly finding the length. Here is the revised version:

  def tailsThatLength: List[Int] = {
    // Compute the length once –
    val n = nums.length
    // Note how the *range* "(n-1) to 0 by -1" is a first-class
    // value, which can occur in other contexts than a for-loop.
    // We do have to convert it to a list before we can zip it
    // with another list –
    val boolPairs = (nums zip ((n-1 to 0 by -1).toList)).filter({
      case (num, afterCount) => num == afterCount
    })
    boolPairs.map({
      case (num, _) => num
    })
  }

A perhaps better version of the second case of doubledElts is

    case _ :: t => (nums zip t).foldRight(List(false))((nextPair, listFromRight) =>
      (nextPair._1 == nextPair._2) :: listFromRight)

This version avoids building a possibly long list and then copying it as ::: must do.

2 Here is the code for addKeyVal

  def addKeyVal(newKey: Double, newVal: A): DBinaryTree[A] = this match {
    case DEmpty() => DLeaf(newKey, newVal)

    case DLeaf(oldKey, oldVal) => {
      // We make a new DLeaf, which will go either left or right
      // (or, perhaps, replace this leaf) –
      val newKeyLeaf = DLeaf(newKey, newVal)
      // Equality of keys is questionable …
      if (newKey == oldKey) newKeyLeaf
      else {
        val split = (newKey + oldKey)/2
        if (newKey < split) DIntNode(newKeyLeaf, split, this)
        else DIntNode(this, split, newKeyLeaf)
      }
    }

    case DIntNode(left, num, right) => {
      if (newKey < num) {
        DIntNode(left.addKeyVal(newKey, newVal),
                 num,
                 right)
      } else {
        DIntNode(left,
                 num,
                 right.addKeyVal(newKey, newVal))
      }
    }
  }

3 Here are the basic parts of the definitions of the various classes involved:

trait TreeList[A] {
  ...
}

case class TreeListLeaf[A](data: List[A]) extends TreeList[A] {}

case class TreeListNode[A](subLists: List[TreeList[A]]) extends TreeList[A] {}

/** The companion object for trait TreeList.  
  * Supplies a "static" constant, plus the method sum --
  */
object TreeList {
  /** This variable has an uppercase name because it is a
    * constant (a val bound in an Object).
    * Its type (String, String) means "ordered pair of strings."
    * Its value is the open bracket and the close bracket
    * for TreeLists.
    */
  final val TreeListBrackets: (String, String) = ("[", "]")
  ...
}

The ellipses will be filled in as we go. The purpose of the constant TreeListBrackets will be explained in part 3C.

3A Here is the definition of sum, which goes into the object TreeList:

  def sum(itl: TreeList[Int]): Int = itl match {
    case TreeListLeaf(dl) => dl.foldLeft(0)(_+_)
    case TreeListNode(stl) => {
      def combine(sumFromLeft: Int, st: TreeList[Int]): Int = {
        sumFromLeft + sum(st)
      }

      stl.foldLeft(0)(combine)
    }
  }

The reason why sum is in the companion object is that it applies only to TreeLists of Ints. There's no natural way to specialize it to this case within the definition of TreeList.

3B This definition of flatten goes into the trait definition:

  def flatten: List[A] = this match {
    case TreeListLeaf(dl) => dl
    case TreeListNode(stl) => {
      def appendToRes(st: TreeList[A], resFromRight: List[A]): List[A] = {
        st.flatten ::: resFromRight
      }

      // In the last line of `flatten`, we need to say
      // `List[A]()`, instead of simply `List()` or `Nil`, to help the
      // compiler.  This is "explained" (up to a point) in Lecture
      // Note 5. --
      stl.foldRight(List[A]())(appendToRes)
    }

We try hard to avoid ":::", but in this case it's unavoidable. It's still better to use right-recursion here than left-, so that we copy each recursively obtained result just once. But flatten(Treelist[[[...[a₁] ₂] ... ] a_N]) still takes time proportional to N². If N is large (i.e., if the structure is very deep), an even more efficient idea would be to make a list of all the leaf lists, then append them using foldRight so that every leaf list is copied exactly once. Fortunately, most trees are not that deep. If N is the size of their contents, their depth tends to be about log N. That's why they're useful.

The reason we can put flatten into the trait definition is that it works for any kind of TreeList, any element-type A.

3C Here is the definition of toString, which goes into the trait definition

  override def toString: String = {
     "TreeList" ++ treeListString
  }

  /** Produce a string representation of a TreeList, as if it were a
    * structure of lists from a language in which parentheses automatically
    * delimited lists.
    */
  def treeListString: String = {
    val (open, close) = TreeListBrackets
    this match {
      case TreeListLeaf(objl) => objl.mkString(open, ", ", close)
      case TreeListNode(subl) => {
        subl.map(_.treeListString).mkString(open, ", ", close)
      }
    }
  }

The reason why we define a constant TreeListBrackets is just the general principle that literals should occur in just one place. Without the constant, the occurrences of open and close would be replaced by "[" and "]", and each would appear twice. Now, in this case there is unlikely to be much confusion, and I don't much care whether you bothered to use the constant (or to define your own). But in general the reader of a program is likely to be baffled by the purpose of an arbitrary literal, and will often ask whether two equal literals are meant to be the same or are the same by coincidence.^Bafflement

Note the escape clause "in just one place." If a literal is used in just one place in the entire program, that place doesn't have to be the definition of a constant. However, whatever comments would appear at the definition of a constant should appear in that one place. To choose a hypothetical example:

       // The open bracket "[" will be balanced by a single "]"
       // produced by the call to `recurse`.  The resulting string
       // shows the list structure of the Treelist tl --
       val outputString = "[" ++ recurse(tl)