Go to the profile of Yulin Chen
Yulin Chen

Functional Programming Principles in Scala week 3 — Data And Abstraction

第三週內容，突然不「函數式」了，主題是 Scala 的類別和物件

這週的教學影片內容，比起前兩週，我覺得更難以消化了…，不過這也讓我體會 Mooc 的一個好處，如果是在實體教室上課，教授上的鳥，通常還是得被迫坐在那裡把剩下的時間耗完才能走人，但是 Mooc ，隨時暫停、隨時繼續都沒問題，可以找對個人更適合的教材或資源把課程內容補起來，不一定要整堂課上完，簡單講，就是學習更彈性了

我在看完前兩個教學影片後，就直接做作業，語法、語言特性，這種東西不必死記，實際遇到、需要用到時，翻參考手冊、知道關鍵字怎麼查就好，比起一直聽別人講這些，還是實際想問題跟實作，會比較深刻和踏實，這週筆記會主要集中記錄關於作業的思考和 debug 過程

Assignments 目標

這週的題目也相當有趣，而且貼近實際應用：「儲存 tweet 的資料結構，並實作幾個指定的介面方法」（Twitter 的 tweet 資料極簡化版）

這次作業給定了一個抽象類別 TweetSet ，裡面有幾個抽象方法待實作， TweetSet 有兩個實體子類別 Empty, NonEmpty

NonEmpty 會儲存一篇 tweet 的資料在它的一個 Tweet 成員，並且用 left 參考左邊的 sub TweetSet ，用 right 參考右邊的 sub TweetSet

Tweet 會儲存一篇 tweet 的文字、作者、 retweet 數

在把一堆 TweetSet 組在一起時，會根據各個 Tweet 成員內的字串來排序、構成 binary search tree （每個節點都是一個 TweetSet 物件）

作業會用到的相關 Scala 語言特性

抽象類別裡面可以有定義好的方法

abstract class C {
  def f: Int
  def g: Int = 1
}

物件和類別可以繼承自一個 Trait ， Scala 的 Trait 類似 Java 的 Interface ， Trait 裡的方法可以有實作

trait TweetList {
  def head: Tweet
  def tail: TweetList
  def isEmpty: Boolean
  def foreach(f: Tweet => Unit): Unit =
    if (!isEmpty) {
      f(head)
      tail.foreach(f)
    }
}
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
}

要覆蓋抽象父類別裡的方法，必須在實體子類別的方法定義前面加上 override 關鍵字

abstract class C {
  def f: Int
}
class D extends C {
  override def f: Int = 1
}

難點 — 在抽象的父類別還是實體的子類別定義方法？

要思考它指定實作的幾個方法，是要定義在抽象的父類別裡面，還是實體的子類別裡面，大致想法是「可以在子類別通用的，就寫在父類別，如果子類別要做的事都不一樣，那就在個別子類別裡面定義」

上述提到， NonEmpty 物件有成員： left, right ，分別參考目前 TweetSet 左邊的 sub TweetSet, 右邊的 sub TweetSet ，這點是跟 TweetSet, Empty 本質上的不同，一個 Empty 物件代表一個「空節點」，沒有 left, right 成員， TweetSet 是一個抽象類別、無法產生物件、也沒有 left, right 成員

我發現當我在思考指定實作的方法要定義在抽象的父類別 TweetSet ，還是在實體的子類別 Empty, NonEmpty 時，主要是根據程式碼需不需要提及「 left, right 」這種「子類別才有的成員」而定，若在 TweetSet 或 Empty 的方法定義裡面提及「 left, right 」，會發生 value not found 的錯誤，因為 TweetSet 和 Empty 並不具備這兩個成員，所以若一個待實作的抽象方法需要提及「左邊的 sub TweetSet, 右邊的 sub TweetSet」，勢必要在實體的子類別定義各自的方法了

難點 — 難以理解的遞迴呼叫

union 目標要把兩個 TweetSet 「聯集」，組成新的 binary search tree ，因為牽涉到要提及 left, right ，所以在 Empty 和 NonEmpty 裡各別實作，我在 NonEmpty 的 union 這樣寫：

class NonEmpty(elem: Tweet, left: TweetSet, right: TweetSet) extends TweetSet {
  // ...
  override def union(that: TweetSet): TweetSet =
    right.union(left.union(that.incl(elem))
)

禮拜六下午寫完，第一次提交，測資過了，但是隔天早上 debug ，看到這段就愣住了…

先解釋一下 incl ，它是 Empty, NonEmpty 裡預先定義好的一個方法，如果整個 binary search tree 結構裡面沒有任何一個 TweetSet 有這個 TweetSet 的 tweet 內容，就 `include` 進來，已經有的話，就不做任何變動

上述 union 程式碼，其實就是一直遞迴下去，只要確保 binary search tree 的每個節點都會被 `include` 到，就能產生正確的聯集結果，我在寫這段時，仔細好好想了一下 union 程式碼執行流程到底是怎樣（代表我禮拜六時根本是剛好矇對，可能是之前修過資料結構的關係吧，一點直覺還是有…），查了一下書，發現術語叫做 binary tree preorder traversal ，這很難用文字說明，先上圖：

遍歷的順序如最左圖，圈圈內的數字所示，會從根節點優先往左遍歷，「直到不能再左了，才回父節點往右邊的兄弟節點」，但是到了右邊的兄弟節點時，「一樣繼續優先往左，直到不能再左，回父節點往右邊的兄弟節點」，重複此流程，直到遍歷完整顆二元樹

遞迴的程式碼很簡短，但是如果可讀性極差，最好還是不要使用

難點 — 找二元樹 retweet 值最大的節點程式碼 debug

我的第一次提交，顯示我根據 TweetSet 的 Tweet 的 retweet 值遞減條列 tweet 的程式碼有錯，測資執行結果一開始會規規矩矩的遞減，到了某個時候會開始忽大忽小條列，表示實作這功能相依的程式碼或方法定義可能有錯

雖然測資只有顯示我這部分有錯，但是看到上述那段 union 的程式碼時，因為一時想不明白那段程式到底做什麼，所以也不禁懷疑，錯誤會不會是發生在測資沒測到的地方？這樣要找的範圍實在不小，我來來回回檢視 TweetSet, Empty, NonEmpty 好幾次，大概花一小時在「看程式碼跟想程式碼在某些情況下有沒有錯」上面，後來想，可能要寫個 failed test 捕捉這個錯誤，可是一時也沒頭緒要怎麼寫，就決定先把條件判斷的過程印到 console 看看再說

不過， Scala IDE for Eclipse 的 console 似乎顯示訊息量有限制，所以沒看到奇怪的結果，跑去看看有沒有辦法提高上限，或是改輸出結果到檔案來看，發現都有點麻煩，最後鎖定排序結果開始忽高忽低那部份的 retweet 數字有哪些，搜尋來看，終於發現問題…

我看到一筆 49 / 13 \ 49 （左節點 / 本節點 \ 右節點）的回傳結果是 13 ，頓時領悟原來是條件判斷出了問題，與我的程式碼邏輯等價的虛擬碼如下：

if (left.retweets > right.retweets && left.retweets > this.retweets) {
  left
} else if (right.retweets > left.retweets && right.retweets > this.retweets) {
  right
} else {
  this
}

因為 left 要嚴格大於 right 和本身的 retweets 才會回傳 left ， right 也要嚴格大於 left 和本身的 retweets 時才會回傳 right ，前兩者都不成立的話，就回傳本身，造成上述那種明明左節點、右節點都比本節點大，左右相等，卻因不滿足「嚴格大於另外兩者」的條件，而回傳本節點的錯誤結果…

一些無關技術的作業心得

仔細想想，這門 Mooc 到目前為止的作業，都是給定一些別人寫好的程式碼和（部分）自動化測試，指定實作特意挖空的部分，來學習當週課程的主題，之前在學校做程式設計課相關的作業時好像沒有這種經驗，幾乎都是給規格和題目，就要把程式碼從無到有兜出來，如果沒跟同學、朋友「互相參考」的話，其實不太有「讀別人怎樣實作同樣功能的程式碼」的機會

相對的，這門 Mooc 的做法，要閱讀不短的問題說明文字、搞清楚別人寫好的程式碼在做什麼、思考如何用現有的函數兜出指定實作的功能，所以比起之前在學校的那種經驗，這樣比較能訓練到「閱讀程式碼」的能力