CS 252

Spring 2008

Lab #5

  1. Using the Tree datatype from the lecture, how do you declare a tree mytree that looks like this:
       *
      / \
     *   3
    / \ 
    1 2
  2. Write a function height that computes the height of a tree (i.e. the longest path from the root to a leaf). The height of mytree should be 3.
  3. The Tree datatype declaration only stores values in the leaves of the tree. How do you modify it to store values in every node, like you did in your data structures class?
  4. With that definition, how do you make a tree mytree that looks like this:
       1
      / \
     2   3
    / \ / \
    4 5 6 7
  5. How can you make a tree like this?
       1
      / \
     2   3
    / \ / 
    4 5 6

    (You may need to change your tree definition.)

  6. Look up the definition of the class :: in the Scala API. Note that it is a case class. Look up the definition of Nil. It is a case object. Scala has a special construct for classes with a single instance—more about that in the next lecture. That means you can use these in a match expression. Write a version of firstN (see the previous lab) that uses match but not head, tail, or isEmpty.
  7. Consider the polynomial example from the lecture. It is disappointing that the resulting derivative looks so complicated. Here is a first effort at defining a function for simplifying the result: 
    def simplify(p: Poly) : Poly = p match {
  case Prod(f, Const(1.0)) => f
  case Sum(f, g) => Sum(simplify(f), simplify(g))
  case _ => p
}

    What happens when you simplify the derivate of x2 + x with this function?

  8. That's nice, but surely you can do better. How do you eliminate the Prod(Const(1.0),X())?
  9. That's even nicer, but how can you get at the form 2x + 1? Hint: 
    case Sum(f, g) => { val fs = simplify(f) ; val gs = simplify(g) ; if (fs == gs) ... else ... }

    (In Scala, == is structural equality, not reference equality.)

  10. What is the derivative of x3 with these definitions? (The result is easier to read if you call simplify)
  11. It would be desirable to have a power term. Define another case class Pow(p, n) where p is a polynomial and n is an integer. Extend the definition of deriv to that case class. (Recall that the derivative of pn is n pn-1 p', where p' is the derivative of p. What is simplify(deriv(Pow(X(), 3))?