pty，对于空集来说，空集和任何一个集合的并集都是参数所代表的那个集合，所以直接返回参数表示的集合就可以了。

NonEmpty来说，按照之前的思路，需要先将对应二叉树的跟加入，再一次将左右子树作为union的参数传入已经加入了二叉树根的集合。当然每次都需要保存调用集合前一次操作后得到的集合作为下一步操作的参数。

很简单啦，去实现吧。

Sorting Tweets by Their Influence

这一部分是完成对一个TweetSet的排序，返回一个TweetList。TweetSet.scala中也定义了一个特质TweetSet，表示一个列表：

trait TweetList {
  def head: Tweet
  def tail: TweetList
  def isEmpty: Boolean
  def foreach(f: Tweet => Unit): Unit =
    if (!isEmpty) {
      f(head)
      tail.foreach(f)
    }
}

我们可以看到这是一个列表的典型表示方法，head为一个Tweet类对象，tail是除掉head之外的元素组成的一个列表。

TweetSet其中包含两个实现，一个是空的列表Nil，另外一个是非空列表Cons：

object Nil extends TweetList {
  def head = throw new java.util.NoSuchElementException("head of EmptyList")
  def tail = throw new java.util.NoSuchElementException("tail of EmptyList")
  def isEmpty = true
}

class Cons(val head: Tweet, val tail: TweetList) extends TweetList {
  def isEmpty = false
}

可以看到Nil的head和tail都是一个会抛出异常的元素访问，并且不可能出现多个空列表实例，这里Nil被定义成为一个单例对象，即Object。

Cons的元素就包含两个，一个是Tweet类对象的head，另外tail作为列表出现。

扯得有点远，回过头来说，如果从一个TweetSet开始，按照retweet大小（即影响的高低）将元素重新排列成为一个TweetList，那么就要从Nil开始，做以下几步动作：

1.每次挑选出retweet数量最大的Tweet节点

2.将挑选出来的节点加入到要返回的TweetList中

3.在原来的TweetSet中删除掉这个节点

这三个过程连接起来就组成了按照影响力排序这个函数，其函数签名如下：

def descendingByRetweet: TweetList

可以看到这个方法没有参数，返回值是一个TweetList对象。

从以上列出的3点出发，继续看题目，发现第3步已经有相应的方法实现了：

  def remove(tw: Tweet): TweetSet =
    if (tw.text < elem.text) new NonEmpty(elem, left.remove(tw), right)
    else if (elem.text < tw.text) new NonEmpty(elem, left, right.remove(tw))
    else left.union(right)

那我们只需要做第1、2步的工作就OK了。

首先看第一步，第一步需要完成的工作在TweetSet这个抽象类中也有给出原型：

def mostRetweeted: Tweet =

这里没有给出实现，因为这里不需要。但是我们需要在Empty和NonEmpty中分别实现这个方法，一个空集应该如何返回它里面最受欢迎的推特呢？我们可以使用特殊的字符来标记，比如返回使用-1表示retweet数量的Tweet对象。

NonEmpty中呢？按照之前的思路，当然是比较其对应的二叉树根元素和左右子树的mostRetweeted元素谁更受欢迎，然后返回最受欢迎的那个。定义三个Tweet对象，分别表示根元素、左子树retweet最大的元素也就是左子树的mostRetweet的结果以及右子树retweet最大的元素，然后通过比较返回retweet最大的那个元素。因为左右子树的左右子树的左右子树（有限次循环后）最终是一个空集，我们对空集的定义决定了这个递归最终会返回结果，并且得到的Tweet对象有最大的retweet数量。

第二部分的工作就是将得到的最流行的Tweet加入到列表中并返回，当然这里需要判断如果返回的Tweet的转发量为-1（我们前面定义的魔鬼数字）的话，就需要返回Nil，表示空集的排序结果仍然是空列表。否则需要返回最流行的Tweet为head，原TweetSet删除这个最流行的Tweet之外剩下的集合按照retweet数量排序得到的列表为tail的列表。求出tail这部分的描述是不是有点绕？简单来说就是将原有的TweetSet删除最流行的节点之后，再调用descendingByRetweet得到的列表。

看，又是一次漂亮的递归。

Tying everything together

以上完成了filter、union和排序功能，现在我们可以做一点小事情了。比如说在一堆推中选择被转发次数最多的一批。作业工程中的TweetReader.scala中包含了一批推特数据，作业中已经完成了对她们的汇总，通过调用TweetReader.allTweets可以返回这些推特的集合，使用一个TweetSet对象表示。

另外TweetSet.scala中给出了两个关键词列表：第一个列表包含一系列Google和Android相关的词汇，第二个列表包含一系列Apple和iOS相关的词汇。

作业首先要求完成对两个TweetSet的赋值，googleTweets包含所有text中提到第一个词汇列表中所有词汇的Tweet对象，appleTweets中包含所有text中提到第二个词汇列表中所有词汇的Tweet对象。这两个TweetSet对象都是lazy变量（关于这个变量的用法后续我们会介绍），其签名如下：

lazy val googleTweets: TweetSet
lazy val appleTweets: TweetSet

将这两个变量赋值之后，作业还要求将其并集中的元素按照retweet数量来排序，即完成以下函数体：

 /**
   * A list of all tweets mentioning a keyword from either apple or google,
   * sorted by the number of retweets.
   */
  lazy val trending: TweetList =

首先看这两个变量的赋值，当然需要首先定义一个变量来存储所有的推特，这个TweetSet对象的赋值就不多说了，一条语句就能搞定。

然后我们需要使用filter方法对推特全集进行过滤，过滤条件是什么呢？当然是是否包含相应列表中的词汇。所以filter的参数表示的判定条件就应该是是否至少包含一个列表中的词汇。

两个TweetSet的获取方法类似，只是传入的变量不同而已。

trending这个方法就更简单了，将得到的googleTweets和appleTweets做一次union操作，使用得到的并集调用排序方法即可。

结语

在这个作业中强调的地方有两点：1.注意这些类都是immutable的，也就是说对类对象做的操作不会修改原有对象的值，而是通过返回一个新对象的形式来体现，这也是函数式编程中一个很重要的概念即闭包（closure）；2.由于TweetSet和Tw

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

Tying everything together

结语