Scala 下的 Functional 資料結構 (2)

在 Functional 資料結構中的資料分享

當資料為不可變的情況下,可以的話我們會希望能夠重用所有資料,盡量減少複製情況發生,就稱做 資料分享 (data sharing)

假設我們想幫 List 在最前面的地方加上節點 a,我們可以用以下方式重用已在記憶體的資料,而不是複製它,

以相同邏輯脈絡來看,當我們想在 List 中刪除頭節點,實際上也只是把 tail 的參照回傳回去而已,a 的資料還是存在在記憶體中,直到被記憶體回收機制回收。


Exercise D4-1

實做 setHead function,它能讓我們更新頭節點的值,需考量到輸入可能是空 List 的情況。

def setHead[A](l: List[A], head: A): List[A] 

Exercise D4-2

實做 drop function,它能讓我們從 List 中移除前 n 個節點。

def drop[A](l: List[A], n: Int): List[A]

讓我們來看另一個使用資料分享的案例 append,該 function 能新增 a2 到 a1 後面,

  def append[A](a1: List[A], a2: List[A]): List[A] =
    a1 match
      case Nil => a2
      case Cons(h, t) => Cons(h, append(t, a2))

此 append function 的時間、空間複雜度是以 a1 為主,因為我們只複製了 a1,而欲新增的 a2 我們直接使用,不做任何複製,

想像一下若要 append 的結構是 array,你務必要在記憶體 new 包含 a1, a2 長度的 array 空間,然後在把 a1, a2 元素複製過去才行。

List 的遞迴

我們回頭看一下 Scala 下的 Functional 資料結構 (1) 的 List companion object 中有定義的 2 個 function,

  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)

我們可以觀察到,這 2 個 function 都是基於一個初始值,然後使用遞迴的方式遍歷所有元素,在依 *+ 去計算結果;所以基於 DRY (Don’t Repeat Yourself) 原則,我們可以抽象成這樣,

  def foldRight[A, B](as: List[A], z: B, f: (A, B) => B): B = as match
    case Nil => z
    case Cons(x, xs) => f(x, foldRight(xs, z, f))

z 是初始值,f 是我們可自定義的 high-order function,我們一樣使用遞迴去遍歷所有元素,然後將之前計算的結果,以及目前的值當做參數傳入給 f,並且使用多型 A, B 來讓此 function 更萬用,

high-order function 是用來定義一個 function (a) 可以把另一個 function (b) 當做參數傳遞過去,

例如 def filter(f: Int => Boolean): Array[Int],filter 能接受一個 function f 做為參數,f 的輸入是 Int,而輸出是 Boolean,

我們可以使用 filter 排除所有 Array 中不符合條件的值,所以我們就可以用這個 filter function 來排除 Array 中所有偶數(以下程式使用 Scala REPL 執行),

scala> val arr = Array(1,2,3)
val arr: Array[Int] = Array(1, 2, 3)


scala> arr.filter((x: Int) => x % 2 == 1)
Array(1, 3)

scala> arr.filter(x => x % 2 == 1)
Array(1, 3)

scala> arr.filter(_ % 2 == 1)
Array(1, 3)

high-order function 有多種寫法,上面 3 種都代表相同意思,若 function 定義單純,則可以使用 _ 代表由左到右的參數使用順序。

BTW Scala 3 跟 Scala 2 的 high-order function 沒有什麼差別就是了。

有了 foldRight 後,我們的 sumproduct 就能改寫成以下這樣,

  def sum(ints: List[Int]): Int = foldRight(ints, 0, _ + _)
  def product(doubles: List[Double]): Double = foldRight(doubles, 1.0 , _ * _)

如果有點難懂,我們可以細部分解一下 sum(List(1, 2, 3)) 這個例子,

foldRight(Cons(1, Cons(2, Cons(3, Nil))), 0, (x,y) => x + y)

1 + foldRight(Cons(2, Cons(3, Nil)), 0, (x,y) => x + y)
1 + (2 + foldRight(Cons(3, Nil), 0, (x,y) => x + y))
1 + (2 + (3 + foldRight(Nil, 0, (x,y) => x + y)))
1 + (2 + (3 + (0)))

6

我們不需要宣告本地變數以及依告修改本地變數的值來計算結果,functional programming 下的許多操作都是用 pattern match 和 遞迴來實現。


Exercise D4-3

使用 foldRight 來實現 function length,它能計算 List 的長度。

def length[A](l: List[A]): Int 

Day 4 – Exercise answer

更多的練習

Exercise D5-1

foldRight 是從 List 的最右邊往左推進,想當然爾,當然也有從左邊開始的 foldLeft

也剛好 foldRitht 並不是 tail-recursive,所以在極端情況下可能會發生 StackOverflowError,而 foldLeft 在實作上是可以符合 tail-recursive,就來試著練習吧!

import scala.annotation.tailrec
​
@tailrec
def foldLeft[A, B](as: List[A], z: B, f: (B, A) => B): B

tail-recursive 是以一個不同的方式來執行 recursive function,它的最後一個操作是呼叫自己,而不會有其它操作,當 Scala 編譯器檢測到 function 是 tail-recursive 時,編譯器會重寫 JVM bytecode,使其能重用 function 的 stack frame,

然後在程式中,我們可以用 @tailrec annotation 來標註某一 function 為 tail-recursive,若 function 不是 tail-recursive,編譯過程中會報錯,

所以這裡有個重點是 呼叫自己,前一天的 foldRight 就不符合這個條件,其 Cons 下的最後一個操作是調用 f,而不是直接呼叫自己。def foldRight[A, B](as: List[A], z: B, f: (A, B) => B): B = as match
case Nil => z
case Cons(x, xs) => f(x, foldRight(xs, z, f))


Exercise D5-2

使用 foldLeft 來實現 function reverse,此 function 能反轉 List 的順序,例如 List(1, 2, 3) 能變成 List(3, 2, 1)。

def reverse[A](as: List[A]): List[A]

Exercise D5-3

使用 foldRight 來實現 function append

def appendViaFoldRight[A](a1: List[A], a2: List[A]): List[A]

Exercise D5-4

使用 foldRight 來實現 function map,此 function 能修改 List 中的每個元素。

def map[A, B](l: List[A], f: A => B): List[B]

Scala 原生的 List 庫

List 在原生的 Scala 基礎庫下已經有支援,這裡是 API 連結我們在之後所有有講到 List 的地方,都會泛指原生庫下的 List

在 List 底下已經定義好許多好用的方法,也包含我們上面所練習的那些,

def take(n: Int): List[A] // 取得 List 的前 n 個元素
def exists(p: A => Boolean): Boolean // 看某個元素是否存在於 List 中
def takeWhile(p: A => Boolean): List[A] // 取得 List 前面所有符合條件的元素,直到某個元素不符合

Scala 原生 List 跟我們自定義 List 最大的差別就是,原生 List 使用 :: 來表示 Cons,所以 Cons(1, Cons(2, Nil)) 會等於 1 :: 2 :: Nil

在 pattern match 時我們可以用 case h :: t 來表示 case Cons(h, t),來避免我們使用巢狀結構來表達比較複雜的資料,例如可以用 h :: h2 :: t 來從 List 中提取前 2 個值。

在 Scala 中,若看到表達式中含有 : 符號,通常代表右邊的變數為主體,例如 h :: t,實際上是 t.::(h)

Trees

List 是一個 ADT (algebraic data type 代數資料型態) 的範例,ADT 就是某種組合型態,由一個或多個資料建構器 (data constructors) 來定義,而每一個資料建構器也都能包含 1 到 多個參數,2 種常見的 ADT 類型為 productsum,這個 文件 裡頭有更詳細的解釋。

product 類型範例:Tuple

Scala 中使用 ("Steven", 35) 來表達 (String, Int),然後我們可以用 _ 來取得特定位置的值,目前 Tuple 型態 支援到 22 個值

scala> val a = ("Steven", 35)
val a: (String, Int) = (Steven,35)
​
scala> a._1
Steven
​
scala> a._2
35

sum 類型範例:List, Tree

除了 List 以外,ADT 也能用來定義其它資料結構,例如 Binary Tree,

enum Tree[+A]:
 case Leaf(value: A)
 case Branch(left: Tree[A], right: Tree[A])

這裡我們一樣也可以用超好用的 pattern match 來操作 Tree。


Exercise D5-5

使用 pattern match 實作 function size,來計算 Tree 中節點數量 (Branch 和 Leaf)。  

def size[A](t: Tree[A]): Int

總結

我們透過自行實做 List 來了解 functional 資料結構 (functional data structure),它就是只使用 pure function 來做事的資料結構,而其重點就是 不可變 (immutable)資料分享 (data sharing),透過 ADT 定義好資料結構後,就可以用 pattern match 和遞迴來遍歷資料,然後完成所有相關操作。


Exercise answer

tshine73
tshine73
文章: 50

發佈留言

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