引言

这周的作业其实有点复杂，需要完成的代码有点多，有点绕。本周的课程主要讲了Scala中的类、继承和多态，作业也很好的从各个方面考察了课程的内容。作业题目工程主要需要完成的部分是TweetSet.scala这个文件中的内容，比较新潮，都是和推特相关。其中定义了一个抽象类TweetSet，以及其的两个子类Empty、NonEmpty，表示空集和非空集。非空集使用二叉树来表示，二叉树的根是一个Tweet类对象，表示一条推特（用天朝的话来说叫做“微博”），一条微博哦不，一条推特包含user、text和retweets三个字段来标识，分别表示此条推的作者、内容以及转发数量。二叉树的左右子树是按照其根的text内容来排序的，左子树所有节点的text在字典序上都小于根节点的text，右子树所有节点的text在字典序上都大于根节点的text。

并注意，所有的类都是immutable类，也就是说所有的操作不会改变自身的内容，而是返回一个经过修改之后的新对象。

题目强调了在做作业之前可以参考一下已经实现的方法contains和incl。我们可以看一下Empty和NonEmpty类中这两个方法的实现：

 def contains(tweet: Tweet): Boolean = false

  def incl(tweet: Tweet): TweetSet = new NonEmpty(tweet, new Empty, new Empty)

def contains(x: Tweet): Boolean =
    if (x.text < elem.text) left.contains(x)
    else if (elem.text < x.text) right.contains(x)
    else true

  def incl(x: Tweet): TweetSet = {
    if (x.text < elem.text) new NonEmpty(elem, left.incl(x), right)
    else if (elem.text < x.text) new NonEmpty(elem, left, right.incl(x))
    else this
  }

以上两段分别是Empty和NonEmpty两个类中contains和incl的实现代码，而它们的父类中相应的方法声明是这样的：

  def incl(tweet: Tweet): TweetSet

  /**
   * Returns a new `TweetSet` which excludes `tweet`.
   */
  def remove(tweet: Tweet): TweetSet

  /**
   * Tests if `tweet` exists in this `TweetSet`.
   */
  def contains(tweet: Tweet): Boolean

我们可以看到在TweetSet中，所有的方法都没有函数体，我们并不需要在抽象类中实现这些方法，因为我们并不会实例化一个抽象类，所以即便实现了方法，也没有调用他们的机会。

NonEmpty中两个方法的实现很简单，因为Empty中不包含任何元素，所以对于所有的contains的方法，只需要返回false即可。而incl方法是在Empty中增加一个元素，空集中增加一个元素之后，就变成了一个NonEmpty，其根是新增加的Tweet对象，而左右子树分别为空。

再来看NonEmpty，contains方法首先判断其根的text和入参的text的字典序关系，如果入参的text小于根的text，说明和入参相同的text只能存在于这个集合的左子树中；反之存在于集合的右子树中。如果入参的text和根的text相同，则返回true。

有没有注意到，判断是否包含其实只是判断了集合中是否有元素的text和入参的相同，而user和retweet两个都没有判断（这里你可以理解为一个bug，但我们认为这是题目出于简单实现的初衷）。

再来看incl方法，如果入参的text小于集合根的text，则将其添加到左子树中，否则加入到右子树中。如果入参的text等于集合的text则表示此元素已经存在于集合中，不需要添加，返回本集合即可。

这里还有一个细节，就是incl不会修改本集合的内容，而是在本集合上做一些操作，然后返回编辑之后的一个新对象（这和题目开始的要求一致）。

Filtering

好了，看完了集合已经实现的两个方法，我们就来分析作业的第一项内容：filtering。

这部分要实现一个filter方法，其入参为一个由一个Tweet对象到boolean值的判定函数，返回一个集合的子集，其中子集中的所有元素都被入参的判定函数判定为true，比如以下这个调用：

tweets.filter(tweet => tweet.retweets > 10)

将返回tweets中所有retweets大于10的元素的集合。

题目给出了一个提示，可以为filter方法添加一个辅助方法filterAcc，两个函数的原型如下：

/** This method takes a predicate and returns a subset of all the elements
 *  in the original set for which the predicate is true.
 */
def filter(p: Tweet => Boolean): TweetSet
def filterAcc(p: Tweet => Boolean, acc: TweetSet): TweetSet

对于Empty来说，这个方法实现很简单，因为Empty中不包含任何元素，所以对于任何判定函数，Empty的自己都是自身，所以返回this即可。

接下来看一下NonEmpty怎么实现这个方法。从前面contains和incl两个方法的模式就可以看出来，一个需要遍历集合才能完成的方法，通常都是先对二叉树的根做操作，其次对二叉树的左右子树分别作操作，这是一个递归遍历的思想。那么具体到filter方法上呢，我们仍然可以先判断集合的根元素是否符合判定函数的条件，如果符合则将其加入我们要返回的集合，接下来就要对左右子树分别作filter操作，这里的左右子树都可以当成一个独立的集合来做，左右子树的左右子树又可以重复之前的操作，这里看起来是否有点熟悉呢？（子又有孙，孙又有子，子子孙孙无穷匮也……）

好吧，那我们需要用一个东东来保存当前已经遍历过的并且符合判定函数的元素，没错，你看到filterAcc的第二个入参为一个TweetSet集合，这正中下怀啊！

所以在filter函数中需要调用filterAcc，因为初始的时候acc中并没有元素，所以这里给它传递一个Empty对象进去。p是判定函数，在传递过程中不能改变。

接下来的关键就是filterAcc怎么实现了，在一个集合中的filterAcc需要首先判断其根，也即是elem是否符合判定函数p，如果符合该怎么办呢？没错，就是将其加入acc，加入的操作可以使用本来已经实现的incl方法来实现。当然，判断完根元素之后，还需要对左右子树分别做同样的操作。需要注意的是在左右子树调用filterAcc时，不要丢弃了之前已经积攒的acc集合，每次调用filterAcc，都需要将acc做修改之后的新集合作为flterAcc的第二个参数传递进去。

本来逻辑比较难，但是题目给出了filterAcc这个提示之后，我们的思路就开阔了很多。这里还是不能忘记每次返回的方法都要是immutable的，也就是每次要返回一个新创建的集合！

Taking Unions

作业的第二个任务是完成union方法，这个方法的入参是另外一个TweetSet对象。union方法就要返回调用者和参数的并集，其签名如下：

def union(that: TweetSet): TweetSet

有了前面的铺垫，这边应该很简单就能想到solution了。同样分成两个部分来讲，第一个是Em

Coursera公开课Functional Programming Principles in Scala习题解答：Week 3(一)

引言

Filtering

Taking Unions