這周的作業其實有點復雜，需要完成的代碼有點多，有點繞。本周的課程主要講了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。
這部分要實現一個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的，也就是每次要返回一個新創建的集合！
作業的第二個任務是完成union方法，這個方法的入參是另外一個TweetSet對象。union方法就要返回調用者和參數的並集，其簽名如下：
def union(that: TweetSet): TweetSet
有了前面的鋪墊，這邊應該很簡單就能想到solution了。同樣分成兩個部分來講，第一個是Empty，對於空集來說，空集和任何一個集合的並集都是參數所代表的那個集合，所以直接返回參數表示的集合就可以了。
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得到的列表。
看，又是一次漂亮的遞歸。
以上完成了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和TweetList的表示方式，很容易使用遞歸的方式來完成函數的作用，在遞歸過程中，不要忘記將上一步得到的結果作為下一步的參數傳入，否則會出現錯誤的哦！
另外，還有兩個地方值得大家細細品味：一個是除了需要完成的函數之外，題目默認給出了很多函數的實現方式，這些實現很符合函數式編程的理念，代碼也寫的很neat，推薦閱讀並從中學習；另外一個是在test路徑下有一個TweetSetSuite測試類，可以通過完善其中的測試用例來檢驗你所編寫的函數的健壯性！
Week3 題目下載地址：http://download.csdn.net/detail/doggie_wangtao/7395957
以往的習題解析：
Coursera公開課Functional Programming Principles in Scala習題解答：Week 2
Coursera公開課Functional Programming Principles in Scala習題解答：Week 1
聲明：
本文為原創，禁止用於任何商業用途，轉載請注明出處：http://blog.csdn.net/asongoficeandfire/article/details/26842279
