CS470/570 Problem Set 3 (PS3): Solutions

1A Here is one recursive solution:

  def removeOne[A](x: A, l: List[A]): List[A] = l match {
    case Nil => Nil
    case y :: ys => if (y == x) then ys else y :: removeOne(x, ys)
  }

1B Here is how to define removeAll using foldRight:

  def removeAll[A](x: A, l: List[A]): List[A] = {

      l.foldRight(Nil)((y: A, r: List[A]) =>
        // r is the result from the right, a list with no occurrences
        // of x 
        if (x == y) then r else y :: r)
    }

It's the natural recursive solution, with the "natural recursion" part abstracted away into the definition of foldRight. (The Nil part is the base case, and the rest is what to do in the recursion case, after you've called the thing recursively to get r.) This won't seem like progress to you until you've written out that recursion a few dozen times.

1C There are many ways to answer question 1C. The answer I sort of had in mind was —

  def removeOneFunctional[A](x: A, l: List[A]): List[A] = {
    val (prefixWithNoXs, suffixStartingWithX) =
      l.span(_ != x)
    (suffixStartingWithX match {
      case Nil => l
      case y :: ys => prefixWithNoXs ::: ys
  })}  

(See the problem set for an explanation of span. Or check the Scala library.) This solution is not as nice as I visualized at the outset. The check for whether suffixStartingWithX is Nil is clunky, and a call to ":::" is something one should always think about when using linked lists. It requires copying its first argument, an overhead we avoided with the recursive solution.

Sometime after releasing the problem set, I realized that the built-in function diff would solve the problem much quicker:

  def removeOneWithDiff[A](x: A, l: List[A]): List[A] = {
    l.diff(List(x))
  }

l1.diff(l2) finds the complement of l1 and l2, the elements of l1 that aren't in l2. But this is no ordinary complement; if an element e appears k times in l2, the first k elements of l1 will not appear in the result. For k=1, this is exactly what we want!

After all this trickery, one may feel that we've missed an opportunity. foldRight abstracts the recursion pattern in functions like removeAll. If we abstract the recursion pattern found in removeOne, maybe we'll have other opportunities to use it and avoid repeating ourselves. Here's one way to do that:

  /** Like foldRight, except (a) it's not a member of List, so we have to pass
    * the list as the first argument (parameter `l`); (b) there's a `maybeStop`
    * parameter, a function of an element of the list (*x*) and the
    * tail after it (*xs*) that returns None or the value to
    * return.  `maybeStop` is called first; as long as the result is
    * None, the recursion happens, and `combine` is called with two
    * arguments: *x* and the value obtained from the recursion, just
    * as for `foldRight`.  When 'maybeStop` returns Some(r), then 
    * the recursion stops and r is returned.
    */
  def foldRightUntil[A,B](l: List[A], z: B)(maybeStop: (A, List[A]) => Option[B],
                                            combine: (A,B) => B):
      B = {
    def doTheRecursion(remaining: List[A]): B = remaining match {
      case Nil => z
      case x :: xs => maybeStop(x, xs) match {
        case Some(r) => r // Done early
        case None => {    // Keep going
          val r = doTheRecursion(xs)
          combine(x, r)
    }}} 

    doTheRecursion(l)
  }

Armed with this new tool, we can define removeOne one last way:

  def removeOneWithFoldRightUntil[A](x: A, l: List[A]): List[A] = {
    foldRightUntil(l, List[A]())(((y: A, r: List[A]) =>
                                  if (y == x) Some(r)
                                  else None),
                                 ((y: A, r: List[A]) =>
                                   y :: r))
  }

The reason we have to say List[A]() instead of Nil as the value of z is that otherwise the type checker decides A, the type variable in foldRightUntil, = Nothing and then can't live with the consequences.^Check

2A Here is an object containing solutions for problems 2A and 2B, to wit, definitions of leftmostTip and expandPath:

object PS3Q2 {

  type Path = List[Int]

  def leftmostTip(tr: CFGsyntaxTree): Option[Path] =
    tr match {
      // First case only at top level
      case CFGtreeEmpty(_) => None
      case CFGtreeLeaf(term, _) => None
      case CFGtreeTip(term, _) => Some(Nil)
      case CFGexpansion(nonterm, subTrees, _, _, _) => {
        def searchThroughSubTrees(subTreesRemaining: List[CFGsyntaxTree],
                                  index: Int): Option[Path] =
          subTreesRemaining match {
            case Nil => None
            case subTree :: moreSubs => {
              leftmostTip(subTree) match {
                case None => searchThroughSubTrees(moreSubs, index + 1)
                // Success! –
                case Some(path) => Some(index :: path)
              }
            }
          }
        // Body of "case CFGexpansion(…) => …" begins here –
        searchThroughSubTrees(subTrees, 0)
      }
  }

But wait! Doesn't that subroutine searchThroughSubTrees fit the pattern that foldRightUntil captures? There's one discrepancy: that extra index argument. No problem: we can use zipWithIndex another function from the Scala collections API, to associate every element with its index up front. The result looks like this:

  def leftmostTip(tr: CFGsyntaxTree): Option[Path] =
    tr match {
      // First case only at top level
      case CFGtreeEmpty(_) => None
      case CFGtreeLeaf(term, _) => None
      case CFGtreeTip(term, _) => Some(Nil)
      case CFGexpansion(nonterm, subTrees, _, _, _) => {
        type IndexedSynTree = (CFGsyntaxTree, Int)
        foldRightUntil(subTrees.zipWithIndex, None: Option[Path])(
           // maybeStop:
          ((subTreePlusIndex: IndexedSynTree,
            remainingTrees: List[IndexedSynTree]) => subTreePlusIndex match {
            case (subTree, index) => 
              leftmostTip(subTree).map((path) => Some(index :: path))
            }),
           // combine:
          ((subTreePlusIndex: IndexedSynTree, resultFromRight: Option[Path]) =>
           resultFromRight)
        )
      }
  }

Not quite as nice, but maybe we'll see a more general way of abstracting the tool we want. (The reason we have to say None: Option[Path] is analogous to the reason we couldn't use z=Nil in removeOneWithFoldRightUntil. We could have said Nil: List[A] instead of List[A](), if that makes the analogy clearer.)

One piece of this version that may be puzzling is this bit of code from the combiner argument to foldRightUntil:

              leftmostTip(subTree).map((path) => Some(index :: path))

Does it make sense to use map on the result returned by leftmostTip? Yes, because (a) if you look it up, it's there in the Option API; and (b) for many purposes, an Option[A] behaves like a List[A] with either 0 elements or 1. That is, None.map(f) = None and Some(x).map(f) = Some(f(x). What's weird in this case is that the x in question is the result of leftmostTip, so it's of type Option[Path]. So if the result returned by leftmostTip is Some(List(p₀, p₁, …)), the result of the map is Some(Some(List(index, p₀, p₁, …))), of type Option(Option(Path)). This seems at first to defy the laws of physics, or at least of good taste. But it's perfectly legal, and actually makes sense. The outer layer of Some is a signal to foldRightUntil. It's peeled off before the value is returned, the value being itself of type Option[Path].

2B But let's get back to business, and back to our object PS3Q2:

  def expandPath(tr: CFGsyntaxTree, path: Path, grammar: CFG):
            List[CFGsyntaxTree] = (path, tr) match {
   case (Nil, CFGtreeTip(nontrm, d)) => {
     def expandUsingRule(lhs: CFGnonterminal, rule: CFGrule, depth: Int):
         CFGexpansion = {
       val subTrees =
         for {
           sym <- rule.rhs
         } yield sym match {
           case term: CFGterminal => CFGtreeLeaf(term, d+1)
           case nt: CFGnonterminal => CFGtreeTip(nt, d+1)
           case CFGempty =>
             throw new Exception("CFGempty found in unexpected place")
         }
       CFGexpansion(nontrm, subTrees, rule, d,
         // The expansion is one level deeper except
         // in the case where the rhs is empty –
         if (rule.rhs.isEmpty) d else d+1)
     }
     // Body of "case (Nil, CFGtreeTip(…)) => …" starts here –
     val rules = grammar.lookupLeft(nontrm)
     rules.map(r => expandUsingRule(nontrm, r, d))
   }
    case (i :: is,
          CFGexpansion(nontrm, expansion, rule, depth, maxDepth)) => {
      if (i < 0 || i >= expansion.length)
        throw new Exception(
          "Bogus index " + i + " in path (expansion length = " +
            expansion.length + ", nontrm = " + nontrm + ")"
        )
      val subTree = expansion(i)
      // Stuff before the path to the tip –
      val beforeStuff = expansion.take(i)
      // Stuff after the path to thetip
      val afterStuff = expansion.drop(i+1)
      // For each way of expanding the path to the subtree, substitute
      // it for the `i`th element of `expansion` –
      expandPath(subTree, is, grammar).map(newTree =>
        CFGexpansion(nontrm,
          beforeStuff ++ (newTree :: afterStuff),
          rule,
          depth,
          // The only way the new tree can provide a higher
          // maxDepth than before is if the new subTree
          // provides it –
          Math.max(maxDepth, newTree.maxDepth))
      )
    }
    case _ => throw new Exception(
      "Path and tree out of synch: path = " + path +
        "\n  Tree = " + tr
    )
  }
}