在 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 能接受一個 functionf做為參數，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 後，我們的 sum 和 product 就能改寫成以下這樣，
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 更多的練習
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): Btail-recursive 是以一個不同的方式來執行 recursive function，它的最後一個操作是呼叫自己，而不會有其它操作，當 Scala 編譯器檢測到 function 是 tail-recursive 時，編譯器會重寫 JVM bytecode，使其能重用 function 的 stack frame，
然後在程式中，我們可以用
@tailrecannotation 來標註某一 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 類型為 product 和 sum，這個 文件 裡頭有更詳細的解釋。
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
35sum 類型範例：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 和遞迴來遍歷資料，然後完成所有相關操作。
