Scala 下的 Functional 資料結構 (1)

functional 資料結構 (functional data structure) 就是只使用 pure function 來做事的資料結構,如同 什麼是 Funcational Programming? 中有提到的,pure function 不能修改某處的資料結構或變數值,以及其它有 side effect 的事情,換句話說就是 不可變 (immutable) 的資料結構,

舉例來說,數字 3 或數字 4 皆是不可變,當我們處理 3 + 4 這種表達式的時候,我們直接得到結果 7 ,而不是修改 3 或 4 的值,

那這是不是代表所有的計算、操作都要複製值才能做呢?那可未必,我們先來看一個基礎的資料結構,Linked List:

enum List[+A]:
 /** 表示為一個空的 List */
 case Nil
 /** Cons 為 constructor 的縮寫,表示為非空的 List,請注意 `tail` 為另一個 List[A],有可能是 `Nil` 或 `Cons` */
 case Cons(head: A, tail: List[A])
​
object List: // `List` 的 companion object,定義許多 List 的相關作業
 def sum(ints: List[Int]): Int = ints match // 使用 pattern match 來加總 List 中的元素
   case Nil => 0 // 若欲加總的是空 list 則給它 0
   case Cons(x,xs) => x + sum(xs) // 把目前的 `x` 加上其他剩下值的加總
​
 def product(doubles: List[Double]): Double = doubles match
   case Nil => 1.0
   case Cons(0.0, _) => 0.0
   case Cons(x,xs) => x * product(xs)
​
 def apply[A](as: A*): List[A] = // 可變參數語法
   if as.isEmpty then Nil
   else Cons(as.head, apply(as.tail*))

這是一個簡單的單向 Linked List 定義。

Scala 3 的 Enum 預設會建立 sealed class,而 sealed 關鍵字是用來限制我們只有在 相同的檔案中 才能定義、擴展其子類,在 Scala 2 時我們得用 sealed trait List[A] 來明確使用 sealed 闗鍵字;

apply function 是 Scala 的語法蜜糖,當我們用 List(1, 2, 3) 時,會被編譯成 List.apply(1, 2, 3);

而 Scala 的可變參數 (Variadic function syntax) 是用來讓 function 能有彈性的接受多個參數;

而 List 的多型 A 型態前有 + 這個符號,代表了 variance annotation,有點難解釋自己去看 文件 吧!

Pattern Match

pattern match 對我們使用 Scala 撰寫 Functional Programming 中佔有相當重要的一席之地,請務必搞懂它。

而我們在 companion object 中,我們有 2 個 function 是使用 Scala 的 pattern match 來實現,pattern match 是一種用 pattern (模式) 來檢查值的機制,一個成功的 match (配對) 也能讓該值被解構成它原來的組成樣子,就當它是吃了 buff 的 java switch 吧,順道一提 case 語句中也能加入 if/else 判斷;

讓我們來看一下 pattern match 的例子:

List(1, 2, 3) = Cons(1, Cons(2, Cons(3, Nil)))

  • List(1, 2, 3) match { case _ => 42 } 其結果為 42,_ 代表了萬用配對。
  • List(1, 2, 3) match { case Cons(h, _) => h } 其結果為 1,我們使用建構模式來確認 List 是不是用 Cons(head, tail) 的方式來建構,然後我們將 head 的值補捉成變數 h,最後其回傳。
  • List(1,2,3) match { case Cons(_, t) => t } 其結果為 List(2,3)。
  • List(1,2,3) match { case Nil => 42 } 因未配對成功,會拋出 MatchError。

我們也能配對比較複雜的結構,

  • List(1,2,3) match { case Cons(1, Cons(2, Cons(v, _))) => v } 其結果為 3,因為前面的結構皆符合。

pattern match 會由上而下的依序配對,可以用下面的 Exercise 來了解是不是真的懂得 pattern match 吧!

Exercise D3-1

result 的值為何?  

val result = List(1,2,3,4,5) match
   case Cons(x, Cons(2, Cons(4, _))) => x
   case Nil => 42
   case Cons(x, Cons(y, Cons(3, Cons(4, _)))) => x + y
   case Cons(h, t) => h + sum(t)
   case _ => 101

Exercise answer

tshine73
tshine73
文章: 50

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *