摘要：第一節函數式范式什么是函數式編程函數式編程英語或稱函數程序設計，又稱泛函編程，是一種編程范型，它將電腦運算視為數學上的函數計算，并且避免使用程序狀態以及易變對象。
第一節 函數式范式
1. 什么是函數式編程
函數式編程（英語：functional programming）或稱函數程序設計，又稱泛函編程，是一種編程范型，它將電腦運算視為數學上的函數計算，并且避免使用程序狀態以及易變對象。函數編程語言最重要的基礎是 λ演算 （lambda calculus）。而且λ演算的函數可以接受函數當作輸入（引數）和輸出（傳出值）。
比起命令式編程，函數式編程更加強調程序執行的結果而非執行的過程，倡導利用若干簡單的執行單元讓計算結果不斷漸進，逐層推導復雜的運算，而不是設計一個復雜的執行過程。
2. 函數式的基本特性
不可變性
無副作用(純函數、引用透明)
惰性計算
高階函數
...
2.1 無副作用
對于程序p，如果它包含的表達式e滿足 引用透明 ，則所有的e都可以被替換為它的運算結果而不會改變程序p的含義。
假設存在一個函數f，若表達式f(x)對所有引用透明的表達式x也是引用透明的，那么這個f是一個 純函數
函數范式其實核心解決的就是副作用的問題, 無論是隔離副作用的IO還是不可變都是為了解決這個問題而存在. 所以對于副作用的理解一定要足夠深刻. 對于GUI開發人員而言副作用尤其無處不在, 實際開發中會使用大量的手法和技巧去隔離它們.
引用透明
引用透明的另一種理解方式是，引用透明的表達式不依賴上下文，可以本地推導，而那些非引用透明的表達式是依賴上下文，并且需要全局推導。
3. 函數式數據結構
3.1 基本數據類型
100個函數操作一種數據結構的組合要好過10個函數操作10種數據結構的組合。
在OOP的世界中，開發者被鼓勵針對具體問題建立專門的數據結構，并以方法的形式，將專門的操作關聯在數據結構上。
而函數式采用了另一種重用思路，它們用很少一組關鍵數據結構（如list、set、map）來搭配專為這些數據結構深度優化過的操作。在這些關鍵數據結構和操作構成的一套運轉機構上，按需要插入另外的數據結構（之后會講解）和高階函數來調整以適應具體問題。
比如在xml解析問題上，java語音xml解析框架繁多，每一種都有自己定制的數據結構和方法語義。而函數式語言Clojure做法相反，它不鼓勵使用專門的數據結構，而是將xml解析成標準的map結構，而Clojure本身有極為豐富的工具可以與map結構相配合，甚至可以說有幾乎無數的方法可以操作這些核心數據結構。只要將之適配到這些已有結構上，就可以以統一的方式完成工作
這種構建思想被稱為"面向組合子編程", 其實是一種真正更加貼近"數據結構+算法"的構建方式, 以后也許會詳細講到
3.2 Sample: 異常處理
fun failingFn2(i: Int): Int {
val y: Int = (throw Exception("fail"))
try {
val x = 42 + 5
return x + y
} catch (e: Exception) {
return 43
}
}
可以證明y不是引用透明的。我們用表達式的值替代y，卻會得到不同的語義
fun failingFn2(i: Int): Int {
try {
val x = 42 + 5
// 引用透明的概念中，表達式可以被它引用的值替代，
// 這種替代保持程序的含義。
// 而我們對 x+y 表達式中的y替代為
// throw Exception("fail")會產生不同的結果
return x + ((throw Exception("fail")) as Int)
} catch (e: Exception) {
return 43
}
}
異常存在的兩個問題
正如我們所討論的，異常破壞了引用透明并引入了上下文依賴，讓替代模型的簡單推導無法適用，并可能寫出令人困惑的代碼
異常不是類型安全的，函數簽名failingFn和(Int) → Int 的函數類型沒有告訴我們可能發生什么樣的異常，導致異常在運行時才能被檢測到。
坊間的一個習慣是建議異常應該只用于錯誤處理而非控制流
檢測異常
Java的異常檢測最低程度地強制了是處理錯誤還是拋出錯誤，但它們導致了調用者對于簽名模板的修改。
但最重要的是它們不適用于高階函數，因為高階函數不可能感知由它的參數引起的特定的異常。
例如考慮對List定義的map函數：
fun map(l: List, f: (A) -> B): List
這個函數很清晰，高度泛化，但與使用檢測異常不同的是，我們不能對每一個被f拋出的異常的檢測都有一個版本的map。
異常的其他選擇
Either類型
sealed class Either {
data class Left(val value: L): Either()
data class Right(val value: R): Either()
}
eg:
data class Person(val name: Name, val age: Age)
data class Name(val value: String)
data class Age(val value: Int)
fun mkName(name: String): Either =
if(name.isEmpty()) Either.Left("Name is empty.")
else Either.Right(Name(name))
fun mkAge(age: Int): Either =
if(age < 0) Either.Left("Age is out of range.")
else Either.Right(Age(age))
fun mkPerson(name: String, age: Int)
: Either =
mkName(name).map2(mkAge(age))
{ n, a -> Person(n, a) }
3.3 函數式數據結構
函數式數據結構被定義為不可變的，函數式數據結構只能被純函數操作。
比如連接兩個list會產生一個新的list，對輸入的兩個list不做改變。
這是否意味著我們要對數據做很多額外的復制？答案是否定的
我們可以先檢驗一下最普遍存在的函數式數據結構：單項列表
sealed class List {
object Nil: List()
data class Cons(val head: A,
val tail: List): List()
}
定義一些基本操作
sealed class List {
...
// 伴生對象
companion object {
fun sum(ints: List): Int =
when(ints) {
is Nil -> 0
is Cons -> ints.head + sum(ints.tail)
}
fun apply(vararg args: A): List =
if (args.isEmpty()) Nil
else Cons(args.head, apply(*args.tail))
fun product(ds: List): Double =
when(ds){
is Nil -> 1.0
is Cons ->
if(ds.head == 0.0) 0.0
else ds.head * product(ds.tail)
}
}
}
伴生對象
除了經常聲明的數據類型和數據構造器之外，我們也經常聲明伴生對象。它只是與數據類型同名的一個單例，通常在里面定義一些用于創建或處理數據類型的便捷方法。
正如之前所說，函數式需要保持不變性，對于類就包括屬性的不變和方法的不變：
屬性不變，所以我們只能使用純函數操作它們，而容納這些操作函數的地方通常就是在伴生對象。
方法不變，所以通常情況下函數范式不鼓勵繼承(這也是為什么Kotlin的類默認不可繼承)，而是鼓勵我們通過各種組合子和接口(在不同語言有不同叫法，Swift叫協議、Scala叫特質，Haskell本來就沒有OO中的“類”概念所以叫做“類型類”)的組合來描述復雜的關系。
用伴生對象是Scala中的一種慣例。Kotlin也引入了它。
關于型變
在sealed class List的聲明里，泛型A前的“out”是一個型變符號，代表A是協變的，類似Java中的“extend”。意味著如果Dog是Animal的子類，那么List是List的子類型。
型變分為三種：
協變 是可以用自己替換需要自己父親的位置而是允許的，也就是當參數需要父類型參數時你可以傳入子類型
逆變 就是可以用父親替換兒子的位置而是允許的，也就是當參數需要子類型的時候可以傳入父類型
不變 就是不能改變參數類型
它是理解類型系統的重要基石，但通常不用太在意型變注釋，不用型變注釋也會使函數簽名簡單些，只是對于接口而言會失去很多靈活性。
模式匹配
Kotlin的模式匹配太簡單了，還是看看Scala的模式匹配吧
sealed trait List[+A]
case object Nil extends List[Nothing]
case class Cons[+A](head: A,
tail: List[A]) extends List[A]
object List {
def sum(ints: List[Int]): Int = ints match {
case Nil => 0
case Cons(x,xs) => x + sum(xs)
}
def product(ds: List[Double]): Double = ds 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) Nil
else Cons(as.head, apply(as.tail: _*))
模式匹配
模式匹配類似一個別致的switch聲明，它可以侵入到表達式的數據結構內部（Kotlin只做到了自動類型轉換）。
Scala中用關鍵字“match”和花括號封裝的一系列case語句構成。
每一條case語句由“=>”箭頭左邊的模式和右邊的結果構成，如果匹配其中一種模式就返回右邊的對應結果。
def product(ds: List[Double]): Double = ds match {
case Nil => 1.0
case Cons(0.0, _) => 0.0
case Cons(x,xs) => x * product(xs)
}
Haskell實現
data List a = Nil | Cons a (List a) deriving (Show)
sum :: List Integer -> Integer
sum Nil = 0
sum (Cons x xs) = x + (sum xs)
product :: List Double -> Double
product Nil = 1
product (Cons 0 t) = 0
product (Cons x xs) = x * product xs
apply :: [a] -> List a
apply [] = Nil
apply (x:xs) = Cons x (apply xs)
Avocado中的模式匹配DSL(早期為Java實現模式匹配開發的小工具)
public Integer sum(List ints) {
return match(ints)
.empty(() -> 0)
.matchF((x, xs) -> x + sum(xs))
.el_get(0);
}
public Double product(List ds) {
return match(ds)
.empty(() -> 1.0)
.matchF(0.0, xs -> 0.0)
.matchF((x, xs) -> x * product(xs))
.el_get(0.0);
}
函數式數據結構中的數據共享
當我們對一個已存在的列表xs在前面添加一個元素1的時候，返回一個新的列表，即Cons(1, xs),既然列表是不可變的，我們不需要去復制一份xs，可以直接復用它，這稱為 數據共享。
共享不可變數據可以讓函數實現更高的效率。我們可以返回不可變數據結構而不用擔心后續代碼修改它，不需要悲觀地復制一份以避免對其修改或污染。
所有關于更高效支持不同操作方式的純函數式數據結構，其實都是找到一種聰明的方式來利用數據共享。
正因如此，在大型程序里，函數式編程往往能取得比依賴副作用更好的性能。
4. 函數式設計模式
函數范式是不同于面向對象的編程范式，如果我們以對象為本，就很容易不自覺地按照對象的術語來思考所有問題的答案。
我們需要改變思維，學會用不同的范式處理不同的問題。
因為函數式世界用來搭建程序的材料不一樣了，所以解決問題的手法也不一樣了。GoF模式在不同的范式下已經發生了許多的變化：
模式已經被吸收為語言的一部分
模式中描述的解決辦法在函數式范式下依然成立，但實現細節有所變化。
由于在新的語言或范式下獲得了原本沒有的能力，產生了新的解決方案。
詳細： Scala與Clojure函數式編程模式：Java虛擬機高效編程
科里化與部分施用
科里化：
(A, B, C) -> D ==> (A) -> (B) -> (C) -> D
//Java lambda
a -> b -> c -> d
部分施用
(A, B, C) -> D ==> (A， C) -> D
記憶模式
對純函數的調用結果進行緩存，從而避免執行相同的計算。
由于在給定參數不變的情況下，純函數始終會返回相同的值，所以我們可以采用緩存的調用結果來替代重復的純函數調用。
所有被記憶的函數必須保證：
沒有副作用
不依賴任何外部信息
Groovy和Clojure有都內建的memoize函數。
Scala和Kotlin可以擴展實現（內部的實現方法可以看做局部作用，關于局部作用最后一章會詳講）
尾遞歸模式
在不使用可變狀態且沒有棧溢出的情況下完成對某個計算的重復執行。
tailrec fun findFixPoint(x: Double = 1.0): Double =
if (x == Math.cos(x)) x
else findFixPoint(Math.cos(x))
Trampoline：蹦床
尾遞歸對函數寫法有嚴格的要求，但一方面有些語言不支持(如Java)，另一方面尾遞歸被大量使用，因此引入了應對棧溢出的通用解決方案：Trampoline
sealed trait Free[F[_],A] {
def flatMap[B](f: A => Free[F,B]): Free[F,B] =
FlatMap(this, f)
def map[B](f: A => B): Free[F,B] =
flatMap(f andThen (Return(_)))
}
case class Return[F[_],A](a: A) extends Free[F, A]
case class Suspend[F[_],A](s: F[A]) extends Free[F, A]
case class FlatMap[F[_],A,B](s: Free[F, A],
f: A => Free[F, B]) extends Free[F, B]
未優化：
val f = (x: Int) => x
val g = List.fill(10000)(f).foldLeft(f)(_ compose _)
scala> g(42)
java.lang.StackOverflowError
Trampoline：
val f: Int => Free[Int] = (x: Int) => Return(x)
val g = List.fill(10000)(f).foldLeft(f) {
(a, b) => x => Suspend(() => a(x).flatMap(b))
}
偽代碼：
FlatMap(a1, a1 =>
FlatMap(a2, a2 =>
FlatMap(a3, a4 =>
...
DlatMap(aN, aN => Return(aN)))))
當程序在JVM中進行函數調用時，它將棧中壓入調用幀。而Trampoline將這種控制邏輯在Trampoline數據結構中顯式地描述了出來。
當解釋Free程序時，它將決定程序是否請求使用Suspend(s)執行某些“作用”，還是使用FlatMap(x,f)調用子程序。
取代采用調用棧，它將調用x，然后通過在結果上調用f繼續。而且f無論何時都立即返回，再次將控制交于執行的run()函數。
這種方式其實可以認為是一種 協程
Scala中的Trampoline采用語言原生的尾遞歸優化實現：
@annotation.tailrec
def runTrampoline[A](a: Free[Function0,A]): A = (a) match {
case Return(a) => a
case Suspend(r) => r()
case FlatMap(x,f) => x match {
case Return(a) => runTrampoline { f(a) }
case Suspend(r) => runTrampoline { f(r()) }
case FlatMap(a0,g) => runTrampoline { a0 flatMap { a0 => g(a0) flatMap f } }
}
}
尾遞歸實現涉及大量后面會講的知識，因此此處不會詳解
FunctionalJava中則直接通過循環替換遞歸的方式實現：
public final A run() {
Trampoline current = this;
while (true) {
final Either>, A> x =
current.resume();
for (final P1> t : x.left()) {
current = t._1();
}
for (final A a : x.right()) {
return a;
}
}
}
OOP開發人員習慣于框架級別的重用；在面向對象的語言中進行重用所需的必要構件需要非常大的工作量，他們通常會將精力留給更大的問題。
函數級別的重用
面向對象系統由一群互相發送消息(或者叫做調用方法)的對象組成。如果我們從中發現了一小群有價值的類以及相應的消息，就可以將這部分類關系提取出來，加以重用。它們重用的單元是類以及與這些類進行通信的消息。
該領域的開創性著作是《設計模式》，至少為每個模式提供一個類圖。在 OOP 的世界中，鼓勵開發人員創建獨特的數據結構，以方法的形式附加特定的操作。
函數級的封裝支持在比構建自定義類結構更細的基礎級別上進行重用，在列表和映射等基本數據結構之上通過高階函數提供定制，從而實現重用。
例如，在下面的代碼中，filter() 方法接受使用一個代碼塊作為 “插件” 高階函數（該函數確定了篩選條件），而該機制以有效方式應用了篩選條件，并返回經過篩選的列表。
List transactionsIds = transactions.parallelStream()
.filter(t -> t.getType() == Transaction.GROCERY)
.collect(toList());
在后面的《函數設計的通用結構》這一節中我們會詳細體會到函數范式中這種高抽象度的重用思想
本章知識點：
函數范式的定義及基本特性
函數式數據結構
函數式設計模式
To be continued
