本章內容
一等成員、高階方法、科裡化以及局部應用
持久化數據結構
生成Java
Stream時的延遲計算和延遲列表模式匹配以及如何在Java中應用
引用透明性和緩存
第13章中，你瞭解了如何進行函數式的思考；以構造無副作用方法的思想指導你的程序設計能幫助你編寫更具維護性的代碼。這一章，我們會介紹更高級的函數式編程技巧。你可以將本章看作實戰技巧和學術知識的大雜燴，它既包含了能直接用於代碼編寫的技巧，也包含了能讓你知識更淵博的學術信息。我們會討論高階函數、科裡化、持久化數據結構、延遲列表、模式匹配、具備引用透明性的緩存，以及結合器。
14.1 無處不在的函數
第13章中我們使用術語“函數式編程”意指函數或者方法的行為應該像“數學函數”一樣——沒有任何副作用。對於使用函數式語言的程序員而言，這個術語的範疇更加寬泛，它還意味著函數可以像任何其他值一樣隨意使用：可以作為參數傳遞，可以作為返回值，還能存儲在數據結構中。能夠像普通變量一樣使用的函數稱為一等函數（first-class function）。這是Java 8補充的全新內容：通過::操作符，你可以創建一個方法引用，像使用函數值一樣使用方法，也能使用Lambda表達式（比如，(int x) -> x + 1）直接表示方法的值。Java 8中使用下面這樣的方法引用將一個方法引用保存到一個變量是合理合法的：
Function<String, Integer> strToInt = Integer::parseInt;
14.1.1 高階函數
目前為止，我們使用函數值屬於一等這個事實只是為了將它們傳遞給Java 8的流處理操作（正如我們在第4~7章看到的一樣），達到行為參數化的效果，類似我們在第1章和第2章中將Apple::isGreenApple作為參數值傳遞給filterApples方法那樣。但這僅僅是個開始。另一個有趣的例子是靜態方法Comparator.comparing的使用，它接受一個函數作為參數同時返回另一個函數（一個比較器），代碼如下所示。圖14-1對這段邏輯進行了解釋。
Comparator<Apple> c = comparing(Apple::getWeight);
圖 14-1 comparing方法接受一個函數作為參數，同時返回另一個函數
第3章我們構造函數創建流水線時，做了一些類似的事：
Function<String, String> transformationPipeline
= addHeader.andThen(Letter::checkSpelling)
.andThen(Letter::addFooter);
函數式編程的世界裡，如果函數，比如Comparator.comparing，能滿足下面任一要求就可以被稱為高階函數（higher-order function）：
-
接受至少一個函數作為參數
-
返回的結果是一個函數
這些都和Java 8直接相關。因為Java 8中，函數不僅可以作為參數傳遞，還可以作為結果返回，能賦值給本地變量，也可以插入到某個數據結構。比如，一個計算口袋的程序可能有這樣的一個Map<String, Function<Double, Double>>，它將字符串sin映射到方法Function<Double, Double>，實現對Math::sin的方法引用。我們在第8章介紹工廠方法時進行了類似的操作。
對於喜歡第3章結尾的那個微積分示例的讀者，由於它接受一個函數作為參數（比如，(Double x) -> x \* x），又返回一個函數作為結果（這個例子中返回值是(Double x) -> 2 * x），你可以用不同的方式實現類型定義，如下所示：
Function<Function<Double,Double>, Function<Double,Double>>
我們把它定義成Function類型（最左邊的Function），目的是想顯式地向你確認可以將這個函數傳遞給另一個函數。但是，最好使用差異化的類型定義，函數簽名如下：
Function<Double,Double> differentiate(Function<Double,Double> func)
其實二者說的是同一件事。
副作用和高階函數
第7章中我們瞭解到傳遞給流操作的函數應該是無副作用的，否則會發生各種各樣的問題（比如錯誤的結果，有時由於競爭條件甚至會產生我們無法預期的結果）。這一原則在你使用高階函數時也同樣適用。編寫高階函數或者方法時，你無法預知會接收什麼樣的參數——一旦傳入的參數有某些副作用，我們將會一籌莫展！如果作為參數傳入的函數可能對你程序的狀態產生某些無法預期的改變，一旦發生問題，你將很難理解程序中發生了什麼；它們甚至會用某種難於調試的方式調用你的代碼。因此，將所有你願意接收的作為參數的函數可能帶來的副作用以文檔的方式記錄下來是一個不錯的設計原則，最理想的情況下你接收的函數參數應該沒有任何副作用！
現在我們轉向討論科裡化：它是一種可以幫助你模塊化函數、提高代碼重用性的技術。
14.1.2 科裡化
給出科裡化的理論定義之前，讓我們先來看一個例子。應用程序通常都會有國際化的需求，將一套單位轉換到另一套單位是經常碰到的問題。
單位轉換通常都會涉及轉換因子以及基線調整因子的問題。比如，將攝氏度轉換到華氏度的公式是CtoF(x) = x*9/5 + 32。
所有的單位轉換幾乎都遵守下面這種模式：
(1) 乘以轉換因子
(2) 如果需要，進行基線調整
你可以使用下面這段通用代碼表達這一模式：
static double converter(double x, double f, double b) {
return x * f + b;
}
這裡x是你希望轉換的數量，f是轉換因子，b是基線值。但是這個方法有些過於寬泛了。通常，你還需要在同一類單位之間進行轉換，比如公里和英里。當然，你也可以在每次調用converter方法時都使用3個參數，但是每次都提供轉換因子和基準比較繁瑣，並且你還極有可能輸入錯誤。
當然，你也可以為每一個應用編寫一個新方法，不過這樣就無法對底層的邏輯進行復用。
這裡我們提供一種簡單的解法，它既能充分利用已有的邏輯，又能讓converter針對每個應用進行定制。你可以定義一個“工廠”方法，它生產帶一個參數的轉換方法，我們希望借此來說明科裡化。下面是這段代碼：
static DoubleUnaryOperator curriedConverter(double f, double b){
return (double x) -> x * f + b;
}
現在，你要做的只是向它傳遞轉換因子和基準值（f和b），它會不辭辛勞地按照你的要求返回一個方法（使用參數x）。比如，你現在可以按照你的需求使用工廠方法產生你需要的任何converter：
DoubleUnaryOperator convertCtoF = curriedConverter(9.0/5, 32);
DoubleUnaryOperator convertUSDtoGBP = curriedConverter(0.6, 0);
DoubleUnaryOperator convertKmtoMi = curriedConverter(0.6214, 0);
由於DoubleUnaryOperator定義了方法applyAsDouble，你可以像下面這樣使用你的converter：
double gbp = convertUSDtoGBP.applyAsDouble(1000);
這樣一來，你的代碼就更加靈活了，同時它又復用了現有的轉換邏輯！讓我們一起回顧下你都做了哪些工作。你並沒有一次性地向converter方法傳遞所有的參數x、f和b，相反，你只是使用了參數f和b並返回了另一個方法，這個方法會接收參數x，最終返回你期望的值x * f + b。通過這種方式，你復用了現有的轉換邏輯，同時又為不同的轉換因子創建了不同的轉換方法。
科裡化的理論定義
科裡化1是一種將具備2個參數（比如，
x和y）的函數f轉化為使用一個參數的函數g，並且這個函數的返回值也是一個函數，它會作為新函數的一個參數。後者的返回值和初始函數的返回值相同，即f(x,y) = (g(x))(y)。當然，我們可以由此推出：你可以將一個使用了6個參數的函數科裡化成一個接受第2、4、6號參數，並返回一個接受5號參數的函數，這個函數又返回一個接受剩下的第1號和第3號參數的函數。
一個函數使用所有參數僅有部分被傳遞時，通常我們說這個函數是部分應用的（partially applied）。
1科裡化的概念最早由俄國數學家Moses Schönfinkel引入，而後由著名的數理邏輯學家哈斯格爾·科裡（Haskell Curry）豐富和發展，科裡化由此得名。它表示一種將一個帶有 n 元組參數的函數轉換成 n 個一元函數鏈的方法。——譯者注
現在我們轉而討論函數式編程的另一個方面。如果你不能修改數據結構，還能用它們編程嗎？
14.2 持久化數據結構
這一節中，我們會探討函數式編程中如何使用數據結構。這一主題有各種名稱，比如函數式數據結構、不可變數據結構，不過最常見的可能還要算持久化數據結構（不幸的是，這一術語和數據庫中的持久化概念有一定的衝突，數據庫中它代表的是“生命週期比程序的執行週期更長的數據”）。
我們應該注意的第一件事是，函數式方法不允許修改任何全局數據結構或者任何作為參數傳入的參數。為什麼呢？因為一旦對這些數據進行修改，兩次相同的調用就很可能產生不同的結構——這違背了引用透明性原則，我們也就無法將方法簡單地看作由參數到結果的映射。
14.2.1 破壞式更新和函數式更新的比較
讓我們看看不這麼做會導致怎樣的結果。假設你需要使用一個可變類TrainJourney（利用一個簡單的單向鏈接列表實現）表示從A地到B地的火車旅行，你使用了一個整型字段對旅程的一些細節進行建模，比如當前路途段的價格。旅途中你需要換乘火車，所以需要使用幾個由onward字段串聯在一起的TrainJourney對像；直達火車或者旅途最後一段對象的onward字段為null：
class TrainJourney {
public int price;
public TrainJourney onward;
public TrainJourney(int p, TrainJourney t) {
price = p;
onward = t;
}
}
假設你有幾個相互分隔的TrainJourney對像分別代表從X到Y和從Y到Z的旅行。你希望創建一段新的旅行，它能將兩個TrainJourney對像串接起來（即從X到Y再到Z）。
一種方式是採用簡單的傳統命令式的方法將這些火車旅行對像鏈接起來，代碼如下：
static TrainJourney link(TrainJourney a, TrainJourney b){
if (a==null) return b;
TrainJourney t = a;
while(t.onward != null){
t = t.onward;
}
t.onward = b;
return a;
}
這個方法是這樣工作的，它找到TrainJourney對像a的下一站，將其由表示a列表結束的null替換為列表b（如果a不包含任何元素，你需要進行特殊處理）。
這就出現了一個問題：假設變量firstJourney包含了從X地到Y地的線路，另一個變量secondJourney包含了從Y地到Z地的線路。如果你調用link(firstJourney, secondJourney)方法，這段代碼會破壞性地更新firstJourney，結果secondJourney也會加被入到firstJourney，最終請求從X地到Z地的用戶會如其所願地看到整合之後的旅程，不過從X地到Y地的旅程也被破壞性地更新了。這之後，變量firstJourney就不再代表從X到Y的旅程，而是一個新的從X到Z的旅程了！這一改動會導致依賴原先的firstJourney代碼失效！假設firstJourney表示的是清晨從倫敦到布魯塞爾的火車，這趟車上後一段的乘客本來打算要去布魯塞爾，可是發生這樣的改動之後他們莫名地多走了一站，最終可能跑到了科隆。現在你大致瞭解了數據結構修改的可見性會導致怎樣的問題了，作為程序員，我們一直在與這種缺陷作鬥爭。
函數式編程解決這一問題的方法是禁止使用帶有副作用的方法。如果你需要使用表示計算結果的數據結果，那麼請創建它的一個副本而不要直接修改現存的數據結構。這一最佳實踐也適用於標準的面向對像程序設計。不過，對這一原則，也存在著一些異議，比較常見的是認為這樣做會導致過度的對象複製，有些程序員會說“我會記住那些有副作用的方法”或者“我會將這些寫入文檔”。但這些都不能解決問題，這些坑都留給了接受代碼維護工作的程序員。採用函數式編程方案的代碼如下：
static TrainJourney append(TrainJourney a, TrainJourney b){
return a==null ? b : new TrainJourney(a.price, append(a.onward, b));
}
很明顯，這段代碼是函數式的（它沒有做任何修改，即使是本地的修改），它沒有改動任何現存的數據結構。不過，也請特別注意，這段代碼有一個特別的地方，它並未創建整個新 TrainJourney對象的副本——如果a是n個元素的序列，b是m個元素的序列，那麼調用這個函數後，它返回的是一個由n+m個元素組成的序列，這個序列的前n個元素是新創建的，而後m個元素和TrainJourney對像b是共享的。另外，也請注意，用戶需要確保不對append操作的結果進行修改，因為一旦這樣做了，作為參數傳入的TrainJourney對像序列b就可能被破壞。圖14-2和圖14-3解釋說明了破壞式append和函數式append之間的區別。
圖 14-2 以破壞式更新的數據結構
圖 14-3 函數式，不會對原有數據結構進行改動
14.2.2 另一個使用Tree的例子
轉入新主題之前，讓我們再看一個使用其他數據結構的例子——我們想討論的對象是二叉查找樹，它也是HashMap實現類似接口的方式。我們的設計中Tree包含了String類型的鍵，以及int類型的鍵值，它可能是名字或者年齡：
class Tree {
private String key;
private int val;
private Tree left, right;
public Tree(String k, int v, Tree l, Tree r) {
key = k; val = v; left = l; right = r;
}
}
class TreeProcessor {
public static int lookup(String k, int defaultval, Tree t) {
if (t == null) return defaultval;
if (k.equals(t.key)) return t.val;
return lookup(k, defaultval,
k.compareTo(t.key) < 0 ? t.left : t.right);
}
// 處理Tree的其他方法
}
你希望通過二叉查找樹找到String值對應的整型數。現在，我們想想你該如何更新與某個鍵對應的值（簡化起見，我們假設鍵已經存在於這個樹中了）：
public static void update(String k, int newval, Tree t) {
if (t == null) { /* 應增加一個新的節點 */ }
else if (k.equals(t.key)) t.val = newval;
else update(k, newval, k.compareTo(t.key) < 0 ? t.left : t.right);
}
對這個例子，增加一個新的節點會複雜很多；最簡單的方法是讓update直接返回它剛遍歷的樹（除非你需要加入一個新的節點，否則返回的樹結構是不變的）。現在，這段代碼看起來已經有些臃腫了（因為update試圖對樹進行原地更新，它返回的是跟傳入的參數同樣的樹，但是如果最初的樹為空，那麼新的節點會作為結果返回）。
public static Tree update(String k, int newval, Tree t) {
if (t == null)
t = new Tree(k, newval, null, null);
else if (k.equals(t.key))
t.val = newval;
else if (k.compareTo(t.key) < 0)
t.left = update(k, newval, t.left);
else
t.right = update(k, newval, t.right);
return t;
}
注意，這兩個版本的update都會對現有的樹進行修改，這意味著使用樹存放映射關係的所有用戶都會感知到這些修改。
14.2.3 採用函數式的方法
那麼這一問題如何通過函數式的方法解決呢？你需要為新的鍵-值對創建一個新的節點，除此之外你還需要創建從樹的根節點到新節點的路徑上的所有節點。通常而言，這種操作的代價並不太大，如果樹的深度為d，並且保持一定的平衡性，那麼這棵樹的節點總數是2d，這樣你就只需要重新創建樹的一小部分節點了。
public static Tree fupdate(String k, int newval, Tree t) {
return (t == null) ?
new Tree(k, newval, null, null) :
k.equals(t.key) ?
new Tree(k, newval, t.left, t.right) :
k.compareTo(t.key) < 0 ?
new Tree(t.key, t.val, fupdate(k,newval, t.left), t.right) :
new Tree(t.key, t.val, t.left, fupdate(k,newval, t.right));
}
這段代碼中，我們通過一行語句進行的條件判斷，沒有採用if-then-else這種方式，目的是希望強調一個思想，那就是該函數體僅包含一條語句，沒有任何副作用。不過你也可以按照自己的習慣，使用if-then-else這種方式，在每一個判斷結束處使用return返回。
那麼，update 和fupdate之間的區別到底是什麼呢？我們注意到，前文中方法update有這樣一種假設，即每一個update的用戶都希望共享同一份數據結構，也希望能瞭解程序任何部分所做的更新。因此，無論任何時候，只要你使用非函數式代碼向樹中添加某種形式的數據結構，請立刻創建它的一份副本，因為誰也不知道將來的某一天，某個人會突然對它進行修改，這一點非常重要（不過也經常被忽視）。與之相反，fupdate是純函數式的。它會創建一個新的樹，並將其作為結果返回，通過參數的方式實現共享。圖14-4對這一思想進行了闡釋。你使用了一個樹結構，樹的每個節點包含了person對象的姓名和年齡。調用fupdate不會修改現存的樹，它會在原有樹的一側創建新的節點，同時保證不損壞現有的數據結構。
圖 14-4 對樹結構進行更新時，現存數據結構不會被破壞
這種函數式數據結構通常被稱為持久化的——數據結構的值始終保持一致，不受其他部分變化的影響——這樣，作為程序員的你才能確保fupdate不會對作為參數傳入的數據結構進行修改。不過要達到這一效果還有一個附加條件：這個約定的另一面是，所有使用持久化數據結構的用戶都必須遵守這一“不修改”原則。如果不這樣，忽視這一原則的程序員很有可能修改fupdate的結果（比如，修改Emily的年紀為20歲）。這會成為一個例外（也是我們不期望發生的）事件，為所有使用該結構的方法感知，並在之後修改作為參數傳遞給fupdate的數據結構。
通過這些介紹，我們瞭解到fupdate可能有更加高效的方式：基於“不對現存結構進行修改”規則，對僅有細微差別的數據結構（比如，用戶A看到的樹結構與用戶B看到的就相差不多），我們可以考慮對這些通用數據結構使用共享存儲。你可以憑借編譯器，將Tree類的字段key、val、left以及right聲明為final執行，“禁止對現存數據結構的修改”這一規則；不過我們也需要注意final只能應用於類的字段，無法應用於它指向的對象，如果你想要對對像進行保護，你需要將其中的字段聲明為final，以此類推。
噢，你可能會說：“我希望對樹結構的更新對某些用戶可見（當然，這句話的潛台詞是其他人看不到這些更新）。”那麼，要實現這一目標，你可以通過兩種方式：第一種是典型的Java解決方案（對對像進行更新時，你需要特別小心，慎重地考慮是否需要在改動之前保存對象的一份副本）。另一種是函數式的解決方案：邏輯上，你在做任何改動之前都會創建一份新的數據結構（這樣一來就不會有任何的對象發生變更），只要確保按照用戶的需求傳遞給他正確版本的數據結構就好了。這一想法甚至還可以通過API直接強制實施。如果數據結構的某些用戶需要進行可見性的改動，它們應該調用API，返回最新版的數據結構。對於另一些客戶應用，它們不希望發生任何可見的改動（比如，需要長時間運行的統計分析程序），就直接使用它們保存的備份，因為它知道這些數據不會被其他程序修改。
有些人可能會說這個過程很像更新刻錄光盤上的文件，刻錄光盤時，一個文件只能被激光寫入一次，該文件的各個版本分別被存儲在光盤的各個位置（智能光盤編輯軟件甚至會共享多個不同版本之間的相同部分），你可以通過傳遞文件起始位置對應的塊地址（或者名字中編碼了版本信息的文件名）選擇你希望使用哪個版本的文件。Java中，情況甚至比刻錄光盤還好很多，不再使用的老舊數據結構會被Java虛擬機自動垃圾回收掉。
14.3 Stream的延遲計算
通過前一章的介紹，你已經瞭解Stream是處理數據集合的利器。不過，由於各種各樣的原因，包括實現時的效率考量，Java 8的設計者們在將Stream引入時採取了比較特殊的方式。其中一個比較顯著的局限是，你無法聲明一個遞歸的Stream，因為Stream僅能使用一次。在接下來的一節，我們會詳細展開介紹這一局限會帶來的問題。
14.3.1 自定義的Stream
讓我們一起回顧下第6章中生成質數的例子，這個例子有助於我們理解遞歸式Stream的思想。你大概已經看到，作為MyMathUtils類的一部分，你可以用下面這種方式計算得出由質數構成的Stream：
public static Stream<Integer> primes(int n) {
return Stream.iterate(2, i -> i + 1)
.filter(MyMathUtils::isPrime)
.limit(n);
}
public static boolean isPrime(int candidate) {
int candidateRoot = (int) Math.sqrt((double) candidate);
return IntStream.rangeClosed(2, candidateRoot)
.noneMatch(i -> candidate % i == 0);
}
不過這一方案看起來有些笨拙：你每次都需要遍歷每個數字，查看它能否被候選數字整除（實際上，你只需要測試那些已經被判定為質數的數字）。
理想情況下，Stream應該實時地篩選掉那些能被質數整除的數字。這聽起來有些異想天開，不過我們一起看看怎樣才能達到這樣的效果。
(1) 你需要一個由數字構成的Stream，你會在其中選擇質數。
(2) 你會從該Stream中取出第一個數字（即Stream的首元素），它是一個質數（初始時，這個值是2）。
(3) 緊接著你會從Stream的尾部開始，篩選掉所有能被該數字整除的元素。
(4) 最後剩下的結果就是新的Stream，你會繼續用它進行質數的查找。本質上，你還會回到第一步，繼續進行後續的操作，所以這個算法是遞歸的。
注意，這個算法不是很好，原因是多方面的2。不過，就說明如何使用Stream展開工作這個目的而言，它還是非常合適的，因為算法簡單，容易說明。讓我們試著用Stream API對這個算法進行實現。
2關於為什麼這個算法很糟糕的更多信息，請參考http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf。
1. 第一步： 構造由數字組成的Stream
你可以使用方法IntStream.iterate構造由數字組成的Stream，它由2開始，可以上達無限，就像我們在第5章中介紹的那樣，代碼如下：
static Intstream numbers{
return IntStream.iterate(2, n -> n + 1);
}
2. 第二步： 取得首元素
IntStream類提供了方法findFirst，可以返回Stream的第一個元素：
static int head(IntStream numbers){
return numbers.findFirst.getAsInt;
}
3. 第三步： 對尾部元素進行篩選
定義一個方法取得Stream的尾部元素：
static IntStream tail(IntStream numbers){
return numbers.skip(1);
}
拿到Stream的頭元素，你可以像下面這段代碼那樣對數字進行篩選：
IntStream numbers = numbers;
int head = head(numbers);
IntStream filtered = tail(numbers).filter(n -> n % head != 0);
4. 第四步：遞歸地創建由質數組成的Stream
現在到了最複雜的部分。你可能試圖將篩選返回的Stream作為參數再次傳遞給該方法，這樣你可以接著取得它的頭元素，繼續篩選掉更多的數字，如下所示：
static IntStream primes(IntStream numbers) {
int head = head(numbers);
return IntStream.concat(
IntStream.of(head),
primes(tail(numbers).filter(n -> n % head != 0))
);
}
5. 壞消息
不幸的是，如果執行步驟四中的代碼，你會遭遇如下這個錯誤：“java.lang.IllegalStateException: stream has already been operated upon or closed.”實際上，你正試圖使用兩個終端操作：findFirst和skip將Stream切分成頭尾兩部分。還記得我們在第4章中介紹的內容嗎？一旦你對Stream執行一次終端操作調用，它就永久地終止了！
6. 延遲計算
除此之外，該操作還附帶著一個更為嚴重的問題： 靜態方法IntStream.concat接受兩個Stream實例作參數。但是，由於第二個參數是primes方法的直接遞歸調用，最終會導致出現無限遞歸的狀況。然而，對大多數的Java應用而言，Java 8在Stream上的這一限制，即“不允許遞歸定義”是完全沒有影響的，使用Stream後，數據庫的查詢更加直觀了，程序還具備了並發的能力。所以，Java 8的設計者們進行了很好的平衡，選擇了這一皆大歡喜的方案。不過，Scala和Haskell這樣的函數式語言中Stream所具備的通用特性和模型仍然是你編程武器庫中非常有益的補充。你需要一種方法推遲primes中對concat的第二個參數計算。如果用更加技術性的程序設計術語來描述，我們稱之為延遲計算、非限制式計算或者名調用。只在你需要處理質數的那個時刻（比如，要調用方法limit了）才對Stream進行計算。Scala（我們會在下一章介紹）提供了對這種算法的支持。在Scala中，你可以用下面的方式重寫前面的代碼，操作符 #::實現了延遲連接的功能（只有在你實際需要使用Stream時才對其進行計算）：
def numbers(n: Int): Stream[Int] = n #:: numbers(n+1)
def primes(numbers: Stream[Int]): Stream[Int] = {
numbers.head #:: primes(numbers.tail filter (n -> n % numbers.head != 0))
}
看不懂這段代碼？完全沒關係。我們展示這段代碼的目的只是希望能讓你瞭解Java和其他的函數式編程語言的區別。讓我們一起回顧一下剛剛介紹的參數是如何計算的，這對我們後面的內容很有裨益。在Java語言中，你執行一次方法調用時，傳遞的所有參數在第一時間會被立即計算出來。但是，在Scala中，通過#::操作符，連接操作會立刻返回，而元素的計算會推遲到實際計算需要的時候才開始。現在，讓我們看看如何通過Java實現延遲列表的思想。
14.3.2 創建你自己的延遲列表
Java 8的Stream以其延遲性而著稱。它們被刻意設計成這樣，即延遲操作，有其獨特的原因：Stream就像是一個黑盒，它接收請求生成結果。當你向一個 Stream發起一系列的操作請求時，這些請求只是被一一保存起來。只有當你向Stream發起一個終端操作時，才會實際地進行計算。這種設計具有顯著的優點，特別是你需要對Stream進行多個操作時（你有可能先要進行filter操作，緊接著做一個map，最後進行一次終端操作reduce）；這種方式下Stream只需要遍歷一次，不需要為每個操作遍歷一次所有的元素。
這一節，我們討論的主題是延遲列表，它是一種更加通用的Stream形式（延遲列表構造了一個跟Stream非常類似的概念）。延遲列表同時還提供了一種極好的方式去理解高階函數；你可以將一個函數作為值放置到某個數據結構中，大多數時候它就靜靜地待在那裡，一旦對其進行調用（即根據需要），它能夠創建更多的數據結構。圖14-5解釋了這一思想。
圖 14-5 LinkedList的元素存在於（並不斷延展）內存中。而LazyList的元素由函數在需要使用時動態創建，你可以將它們看成實時延展的
我們談論得已經很多，現在讓我們一起看看它是如何工作的。你想要利用我們前面介紹的算法，生成一個由質數構成的無限列表。
1. 一個基本的鏈接列表
還記得嗎，你可以通過下面這種方式，用Java語言實現一個簡單的名為MyLinkedList的鏈接-列表-式的類（這裡我們只考慮最精簡的MyList接口）：
interface MyList<T> {
T head;
MyList<T> tail;
default boolean isEmpty {
return true;
}
}
class MyLinkedList<T> implements MyList<T> {
private final T head;
private final MyList<T> tail;
public MyLinkedList(T head, MyList<T> tail) {
this.head = head;
this.tail = tail;
}
public T head {
return head;
}
public MyList<T> tail {
return tail;
}
public boolean isEmpty {
return false;
}
}
class Empty<T> implements MyList<T> {
public T head {
throw new UnsupportedOperationException;
}
public MyList<T> tail {
throw new UnsupportedOperationException;
}
}
你現在可以構造一個示例的MyLinkedList值，如下所示：
MyList<Integer> l =
new MyLinkedList<>(5, new MyLinkedList<>(10, new Empty<>));
2. 一個基礎的延遲列表
對這個類進行改造，使其符合延遲列表的思想，最簡單的方法是避免讓tail立刻出現在內存中，而是像第3章那樣，提供一個Supplier<T>方法（你也可以將其看成一個使用函數描述符void -> T的工廠方法），它會產生列表的下一個節點。使用這種方式的代碼如下：
import java.util.function.Supplier;
class LazyList<T> implements MyList<T>{
final T head;
final Supplier<MyList<T>> tail;
public LazyList(T head, Supplier<MyList<T>> tail) {
this.head = head;
this.tail = tail;
}
public T head {
return head;
}
public MyList<T> tail {
return tail.get; ←─注意，與前面的head不同，這裡tail使用了一個Supplier方法提供了延遲性
}
public boolean isEmpty {
return false;
}
}
調用Supplier的get方法會觸發延遲列表（LazyList）的節點創建，就像工廠會創建新的對象一樣。
現在，你可以像下面那樣傳遞一個Supplier作為LazyList的構造器的tail參數，創建由數字構成的無限延遲列表了，該方法會創建一系列數字中的下一個元素：
public static LazyList<Integer> from(int n) {
return new LazyList<Integer>(n, -> from(n+1));
}
如果嘗試執行下面的代碼，你會發現，下面的代碼執行會打印輸出“2 3 4”。這些數字真真實實都是實時計算得出的。你可以在恰當的位置插入System.out.println進行查看，如果from(2)執行得很早，它試圖計算從2!開始的所有數字，它會永遠運行下去，這時你不需要做任何事情。
LazyList<Integer> numbers = from(2);
int two = numbers.head;
int three = numbers.tail.head;
int four = numbers.tail.tail.head;
System.out.println(two + " " + three + " " + four);
3. 回到生成質數
看看你能否利用我們目前已經做的去生成一個自定義的質數延遲列表（有些時候，你會遭遇無法使用Stream API的情況）。如果你將之前使用Stream API的代碼轉換成使用我們新版的LazyList，它看起來會像下面這段代碼：
public static MyList<Integer> primes(MyList<Integer> numbers) {
return new LazyList<>(
numbers.head,
-> primes(
numbers.tail
.filter(n -> n % numbers.head != 0)
)
);
}
4. 實現一個延遲篩選器
不過，這個LazyList（更確切地說是List接口）並未定義filter方法，所以前面的這段代碼是無法編譯通過的。讓我們添加該方法的一個定義，修復這個問題：
public MyList<T> filter(Predicate<T> p) {
return isEmpty ?
this : ←─你可以返回一個新的Empty<>，不過這和返回一個空對象的效果是一樣的
p.test(head) ?
new LazyList<>(head, -> tail.filter(p)) :
tail.filter(p);
}
你的代碼現在可以通過編譯，準備使用了。通過鏈接對tail和head的調用，你可以計算出頭三個質數：
LazyList<Integer> numbers = from(2);
int two = primes(numbers).head;
int three = primes(numbers).tail.head;
int five = primes(numbers).tail.tail.head;
System.out.println(two + " " + three + " " + five);
這段代碼的輸出是“2 3 5”，這是頭三個質數的值。現在，你可以把玩這段程序了，比如，你可以打印輸出所有的質數（printAll方法會遞歸地打印輸出列表的頭尾元素，這個程序會永久地運行下去）：
static <T> void printAll(MyList<T> list){
while (!list.isEmpty){
System.out.println(list.head);
list = list.tail;
}
}
printAll(primes(from(2)));
本章的主題是函數式編程，我們應該在更早的時候就讓你知道其實有更加簡潔地方式完成這一遞歸操作：
static <T> void printAll(MyList<T> list){
if (list.isEmpty)
return;
System.out.println(list.head);
printAll(list.tail);
}
但是，這個程序不會永久地運行下去；它最終會由於棧溢出而失效，因為Java不支持尾部調用消除（tail call elimination），這一點我們曾經在第13章介紹過。
5. 何時使用
到目前為止，你已經構建了大量技術，包括延遲列表和函數，使用它們卻只定義了一個包含質數的數據結構。為什麼呢？哪些實際的場景可以使用這些技術呢？好吧，你已經瞭解了如何向數據結構中插入函數（因為Java 8允許你這麼做），這些函數可以用於按需創建數據結構的一部分，現在你不需要在創建數據結構時就一次性地定義所有的部分。如果你在編寫遊戲程序，比如棋牌類遊戲，你可以定義一個數據結構，它在形式上涵蓋了由所有可能移動構成的一個樹（這些步驟要在早期完成計算工作量太大），具體的內容可以在運行時創建。最終的結果是一個延遲樹，而不是一個延遲列表。我們本章關注延遲列表，原因是它可以和Java 8的另一個新特性Stream串接起來，我們能夠針對性地討論Stream和延遲列表各自的優缺點。
還有一個問題就是性能。我們很容易得出結論，延遲操作的性能會比提前操作要好——僅在程序需要時才計算值和數據結構當然比傳統方式下一次性地創建所有的值（有時甚至比實際需求更多的值）要好。不過，實際情況並非如此簡單。完成延遲操作的開銷，比如 LazyList中每個元素之間執行額外Suppliers調用的開銷，有可能超過你猜測會帶來的好處，除非你僅僅只訪問整個數據結構的10%，甚至更少。最後，還有一種微妙的方式會導致你的LazyList並非真正的延遲計算。如果你遍歷LazyList中的值，比如from(2)，可能直到第10個元素，這種方式下，它會創建每個節點兩次，最終創建20個節點，而不是10個。這幾乎不能被稱為延遲計算。問題在於每次實時訪問LazyList的元素時，tail中的Supplier都會被重複調用；你可以設定tail中的Supplier方法僅在第一次實時訪問時才執行調用，從而修復這一問題——計算的結果會緩存起來——效果上對列表進行了增強。要實現這一目標，你可以在LazyList的定義中添加一個私有的Optional<LazyList<T>>類型字段alreadyComputed，tail方法會依據情況查詢及更新該字段的值。純函數式語言Haskell就是以這種方式確保它所有的數據結構都恰當地進行了延遲。如果你對這方面的細節感興趣，可以查看相關文章。3
3關於延遲計算，可以參考https://wiki.haskell.org/Haskell/Lazy_evaluation。——譯者注
我們推薦的原則是將延遲數據結構作為你編程兵器庫中的強力武器。如果它們能讓程序設計更簡單，就盡量使用它們。如果它們會帶來無法接受的性能損失，就嘗試以更加傳統的方式重新實現它們。
現在，讓我們轉向幾乎所有函數式編程語言中都提供的一個特性，不過Java語言中暫時並未提供這一特性，它就是模式匹配。
14.4 模式匹配
函數式編程中還有另一個重要的方面，那就是（結構式）模式匹配。不要將這個概念和正則表達式中的模式匹配相混淆。還記得嗎，第1章結束時，我們瞭解到數學公式可以通過下面的方式進行定義：
f(0) = 1
f(n) = n*f(n-1) otherwise
不過在Java語言中，你只能通過if-then-else語句或者switch語句實現。隨著數據類型變得愈加複雜，需要處理的代碼（以及代碼塊）的數量也在迅速攀升。使用模式匹配能有效地減少這種混亂的情況。
為了說明，我們先看一個樹結構，你希望能夠遍歷這一整棵樹。我們假設使用一種簡單的數學語言，它包含數字和二進制操作符：
class Expr { ... }
class Number extends Expr { int val; ... }
class BinOp extends Expr { String opname; Expr left, right; ... }
假設你需要編寫方法簡化一些表達式。比如，5 + 0可以簡化為5。使用我們的域語言，new BinOp("+", new Number(5), new Number(0))可以簡化為Number(5)。你可以像下面這樣遍歷Expr結構：
Expr simplifyExpression(Expr expr) {
if (expr instanceof BinOp
&& ((BinOp)expr).opname.equals("+"))
&& ((BinOp)expr).right instanceof Number
&& ... // 變得非常笨拙
&& ... ) {
return (Binop)expr.left;
}
...
}
你可以預期這種方式下代碼會迅速地變得異常醜陋，難於維護。
14.4.1 訪問者設計模式
Java語言中還有另一種方式可以解包數據類型，那就是使用訪問者（Visitor）設計模式。本質上，使用這種方法你需要創建一個單獨的類，這個類封裝了一個算法，可以“訪問”某種數據類型。
它是如何工作的呢？訪問者類接受某種數據類型的實例作為輸入。它可以訪問該實例的所有成員。下面是一個例子，通過這個例子我們能瞭解這一方法是如何工作的。首先，你需要向BinOp添加一個accept方法，它接受一個SimplifyExprVisitor作為參數，並將自身傳遞給它（你還需要為Number添加一個類似的方法）：
class BinOp extends Expr{
...
public Expr accept(SimplifyExprVisitor v){
return v.visit(this);
}
}
SimplifyExprVisitor現在就可以訪問BinOp對象並解包其中的內容了：
public class SimplifyExprVisitor {
...
public Expr visit(BinOp e){
if("+".equals(e.opname) && e.right instanceof Number && …){
return e.left;
}
return e;
}
}
14.4.2 用模式匹配力挽狂瀾
通過一個名為模式匹配的特性，我們能以更簡單的方案解決問題。這種特性目前在Java語言中暫時還不提供，所以我們會以Scala程序設計語言的一個小例子來展示模式匹配的強大威力。通過這些介紹你能夠瞭解一旦Java語言支持模式匹配，我們能做哪些事情。
假設數據類型Expr代表的是某種數學表達式，在Scala程序設計語言中（我們採用Scala的原因是它的語法與Java非常接近），你可以利用下面的這段代碼解析表達式：
def simplifyExpression(expr: Expr): Expr = expr match {
case BinOp("+", e, Number(0)) => e // 加0
case BinOp("*", e, Number(1)) => e // 乘以1
case BinOp("/", e, Number(1)) => e // 除以1
case _ => expr // 不能簡化expr
}
模式匹配為操縱類樹型數據結構提供了一個極其詳細又極富表現力的方式。構建編譯器或者處理商務規則的引擎時，這一工具尤其有用。注意，Scala的語法
Expression match { case Pattern => Expression ... }
和Java的語法非常相似：
switch (Expression) { case Constant : Statement ... }
Scala的通配符判斷和Java中的default:扮演這同樣的角色。這二者之間主要的語法區別在於Scala是面向表達式的，而Java則更多地面向語句，不過，對程序員而言，它們主要的區別是Java中模式的判斷標籤被限制在了某些基礎類型、枚舉類型、封裝基礎類型的類以及String類型。使用支持模式匹配的語言實踐中能帶來的最大的好處在於，你可以避免出現大量嵌套的switch或者if-then-else語句和字段選擇操作相互交織的情況。
非常明顯，Scala的模式匹配在表達的難易程度上比Java更勝一籌，你只能期待未來版本的Java能支持更具表達性的switch語句。我們會在第16章給出更加詳細的介紹。
與此同時，讓我們看看如何憑借Java 8的Lambda以另一種方式在Java中實現類模式匹配。我們在這裡介紹這一技巧的目的僅僅是想讓你瞭解Lambda另一個有趣的應用。
Java中的偽模式匹配
首先，讓我們看看Scala的模式匹配特性提供的匹配表達式有多麼豐富。比如下面這個例子：
def simplifyExpression(expr: Expr): Expr = expr match {
case BinOp("+", e, Number(0)) => e
...
它表達的意思是：“檢查expr是否為BinOp，抽取它的三個組成部分（opname、left、right），緊接著對這些組成部分分別進行模式匹配——第一個部分匹配String+，第二個部分匹配變量e（它總是匹配），第三個部分匹配模式Number(0)。”換句話說，Scala（以及很多其他的函數式語言）中的模式匹配是多層次的。我們使用Java 8的Lambda表達式進行的模式匹配模擬只會提供一層的模式匹配；以前面的這個例子而言，這意味著它只能覆蓋BinOp(op, l, r)或者Number(n)這種用例，無法顧及BinOp("+", e, Number(0))。
首先，我們做一些稍微讓人驚訝的觀察。由於你選擇使用Lambda，原則上你的代碼裡不應該使用if-then-else。你可以使用方法調用
myIf(condition, -> e1, -> e2);
取代condition ? e1 : e2這樣的代碼。
在某些地方，比如庫文件中，你可能有這樣的定義（使用了通用類型T）：
static <T> T myIf(boolean b, Supplier<T> truecase, Supplier<T> falsecase) {
return b ? truecase.get : falsecase.get;
}
類型T扮演了條件表達式中結果類型的角色。原則上，你可以用if-then-else完成類似的事兒。
當然，正常情況下用這種方式會增加代碼的複雜度，讓它變得愈加晦澀難懂，因為用if-then-else就已經能非常順暢地完成這一任務，這麼做似乎有些殺雞用牛刀的嫌疑。不過，我們也注意到，Java的switch和if-then-else無法完全實現模式匹配的思想，而Lambda表達式能以簡單的方式實現單層的模式匹配——對照使用if-then-else鏈的解決方案，這種方式要簡潔得多。
回來繼續討論類Expr的模式匹配值，Expr類有兩個子類，分別為BinOp和Number，你可以定義一個方法patternMatchExpr（同樣，我們在這裡會使用泛型T，用它表示模式匹配的結果類型）：
interface TriFunction<S, T, U, R>{
R apply(S s, T t, U u);
}
static <T> T patternMatchExpr(
Expr e,
TriFunction<String, Expr, Expr, T> binopcase,
Function<Integer, T> numcase,
Supplier<T> defaultcase) {
return
(e instanceof BinOp) ?
binopcase.apply(((BinOp)e).opname, ((BinOp)e).left,
((BinOp)e).right) :
(e instanceof Number) ?
numcase.apply(((Number)e).val) :
defaultcase.get;
}
最終的結果是，方法調用
patternMatchExpr(e, (op, l, r) -> {return binopcode;},
(n) -> {return numcode;},
-> {return defaultcode;});
會判斷e是否為BinOp類型（如果是，會執行binopcode方法，它能夠通過標識符op、l和r訪問BinOp的字段），是否為Number類型（如果是，會執行numcode方法，它可以訪問n的值）。這個方法還可以返回defaultcode，如果有人在將來某個時刻創建了一個樹節點，它既不是BinOp類型，也不是Number類型，那就會執行這部分代碼。
下面這段代碼通過簡化的加法和乘法表達式展示了如何使用patternMatchExpr。
代碼清單14-1 使用模式匹配簡化表達式
public static Expr simplify(Expr e) {
TriFunction<String, Expr, Expr, Expr> binopcase = ←─處理BinOp表達式
(opname, left, right) -> {
if ("+".equals(opname)) { ←─處理加法
if (left instanceof Number && ((Number) left).val == 0) {
return right;
}
if (right instanceof Number && ((Number) right).val == 0) {
return left;
}
}
if ("*".equals(opname)) { ←─處理乘法
if (left instanceof Number && ((Number) left).val == 1) {
return right;
}
if (right instanceof Number && ((Number) right).val == 1) {
return left;
}
}
return new BinOp(opname, left, right);
};
Function<Integer, Expr> numcase = val -> new Number(val); ←─處理Number對像
Supplier<Expr> defaultcase = -> new Number(0); ←─如果用戶提供的Expr無法識別時進行的默認處理機制
return patternMatchExpr(e, binopcase, numcase, defaultcase); ←─進行模式匹配
}
你可以通過下面的方式調用簡化的方法：
Expr e = new BinOp("+", new Number(5), new Number(0));
Expr match = simplify(e);
System.out.println(match); ←─打印輸出5
目前為止，你已經學習了很多內容，包括高階函數、科裡化、持久化數據結構、延遲列表以及模式匹配。現在我們看一些更加微妙的技術，為了避免將前面的內容弄得過於複雜，我們刻意地將這部分內容推遲到了後面。
14.5 雜項
這一節裡我們會一起探討兩個關於函數式和引用透明性的比較複雜的問題，一個是效率，另一個關乎返回一致的結果。這些都是非常有趣的問題，我們直到現在才討論它們的原因是它們通常都由副作用引起，並非我們要介紹的核心概念。我們還會探究結合器（Combinator）的思想——即接受兩個或多個方法（函數）做參數且返回結果是另一個函數的方法；這一思想直接影響了新增到Java 8中的許多API。
14.5.1 緩存或記憶表
假設你有一個無副作用的方法omputeNumberOfNodes(Range)，它會計算一個樹形網絡中給定區間內的節點數目。讓我們假設，該網絡不會發生變化，即該結構是不可變的，然而調用computeNumberOfNodes方法的代價是非常昂貴的，因為該結構需要執行遞歸遍歷。不過，你可能需要多次地計算該結果。如果你能保證引用透明性，那麼有一種聰明的方法可以避免這種冗余的開銷。解決這一問題的一種比較標準的解決方案是使用記憶表（memoization）——為方法添加一個封裝器，在其中加入一塊緩存（比如，利用一個HashMap）——封裝器被調用時，首先查看緩存，看請求的“（參數，結果）對”是否已經存在於緩存，如果已經存在，那麼方法直接返回緩存的結果；否則，你會執行computeNumberOfNodes調用，不過從封裝器返回之前，你會將新計算出的“（參數，結果）對”保存到緩存中。嚴格地說，這種方式並非純粹的函數式解決方案，因為它會修改由多個調用者共享的數據結構，不過這段代碼的封裝版本的確是引用透明的。
實際操作上，這段代碼的工作如下：
final Map<Range,Integer> numberOfNodes = new HashMap<>;
Integer computeNumberOfNodesUsingCache(Range range) {
Integer result = numberOfNodes.get(range);
if (result != null){
return result;
}
result = computeNumberOfNodes(range);
numberOfNodes.put(range, result);
return result;
}
注意 Java 8改進了
Map接口，提供了一個名為computeIfAbsent的方法處理這樣的情況。我們會在附錄B介紹這一方法。但是，我們在這裡也提供一些參考，你可以用下面的方式調用computeIfAbsent方法，幫助你編寫結構更加清晰的代碼：Integer computeNumberOfNodesUsingCache(Range range) { return numberOfNodes.computeIfAbsent(range, this::computeNumberOfNodes); }
很明顯，方法computeNumberOfNodesUsingCache是引用透明的（我們假設computeNumberOfNodes也是引用透明的）。不過，事實上，numberOfNodes處於可變共享狀態，並且HashMap也沒有同步4，這意味這該段代碼不是線程安全的。如果多個核對numberOfNodes執行並發調用，即便不用HashMap，而是用（由鎖保護的）Hashtable或者（並發無鎖的）ConcurrentHashMap，可能都無法達到預期的性能，因為這中間又存在由於發現某個值不在Map中，需要將對應的“（參數，結果）對”插回到Map而引起的條件競爭。這意味著多個核上的進程可能算出的結果相同，又都需要將其加入到Map中。
4這是極其容易滋生缺陷的地方。我們很容易隨意地使用HashMap，卻忘記了Java文檔中的提示，這一數據結構不是線程安全的（或者簡單地說，由於我們的程序是單線程的，而毫無顧忌地使用）。
從剛才討論的各種糾結中，我們能得到的最大收穫可能是，一旦並發和可變狀態的對象揉到一起，它們引起的複雜度要遠超我們的想像，而函數式編程能從根本上解決這一問題。當然，這也有一些例外，比如出於底層性能的優化，可能會使用緩存，而這可能會有一些影響。另一方面，如果不使用緩存這樣的技巧，如果你以函數式的方式進行程序設計，那就完全不必擔心你的方法是否使用了正確的同步方式，因為你清楚地知道它沒有任何共享的可變狀態。
14.5.2 “返回同樣的對象”意味著什麼
讓我們在次回顧一下14.2.3節中二叉樹的例子。圖14-4中，變量t指向了一棵現存的樹，依據該圖，調用fupdate(fupdate("Will",26, t)會生成一個新的樹，這裡我們假設該樹會被賦值給變量t2。通過該圖，我們非常清楚地知道變量t，以及所有它涉及的數據結構都是不會變化的。現在，假設你在新增的賦值操作中執行一次字面上和上一操作完全相同的調用，如下所示：
t3 = fupdate("Will", 26, t);
這時t會指向第三個新創建的節點，該節點包含了和t2一樣的數據。好，問題來了：fupdate是否符合引用透明性原則呢？引用透明性原則意味著“使用相同的參數（即這個例子的情況）產生同樣的結果”。問題是t2和t3屬於不同的對象引用，所以(t2==t3)這一結論並不成立，這樣說起來你只能得出一個結論：fupdate並不符合引用透明性原則。雖然如此，使用不會改動的持久化數據結構時，t2和t3在邏輯上並沒有差別。 對於這一點我們已經辯論了很長時間，不過最簡單的概括可能是函數式編程通常不使用