本系列的上一篇文章對(duì)函數(shù)式編程思想進(jìn)行了概述，本文將系統(tǒng)地介紹函數(shù)式編程中的常見(jiàn)概念。這些概念對(duì)大多數(shù)開(kāi)發(fā)人員來(lái)說(shuō)可能并不陌生，在日常的編程實(shí)踐中也比較常見(jiàn)。

函數(shù)式編程范式的意義

在眾多的編程范式中，大多數(shù)開(kāi)發(fā)人員比較熟悉的是面向?qū)ο缶幊谭妒健Ｒ环矫媸怯捎诿嫦驅(qū)ο缶幊陶Z(yǔ)言比較流行，與之相關(guān)的資源比較豐富；另外一方面是由于大部分學(xué)校和培訓(xùn)機(jī)構(gòu)的課程設(shè)置，都選擇流行的面向?qū)ο缶幊陶Z(yǔ)言。面向?qū)ο缶幊谭妒降膬?yōu)點(diǎn)在于其抽象方式與現(xiàn)實(shí)中的概念比較相近。比如，學(xué)生、課程、汽車和訂單等這些現(xiàn)實(shí)中的概念，在抽象成相應(yīng)的類之后，我們很容易就能理解類之間的關(guān)聯(lián)關(guān)系。這些類中所包含的屬性和方法可以很直觀地設(shè)計(jì)出來(lái)。舉例來(lái)說(shuō)，學(xué)生所對(duì)應(yīng)的類 Student 就應(yīng)該有姓名、出生日期和性別等基本的屬性，有方法可以獲取到學(xué)生的年齡、所在的班級(jí)等信息。使用面向?qū)ο蟮木幊趟枷?，可以直觀地在程序要處理的問(wèn)題和程序本身之間，建立直接的對(duì)應(yīng)關(guān)系。這種從問(wèn)題域到解決域的簡(jiǎn)單對(duì)應(yīng)關(guān)系，使得代碼的可讀性很強(qiáng)。對(duì)于初學(xué)者來(lái)說(shuō)，這極大地降低了上手的難度。

函數(shù)式編程范式則相對(duì)較難理解。這主要是由于函數(shù)所代表的是抽象的計(jì)算，而不是具體的實(shí)體。因此比較難通過(guò)類比的方式來(lái)理解。舉例來(lái)說(shuō)，已知直角三角形的兩條直角邊的長(zhǎng)度，需要通過(guò)計(jì)算來(lái)得到第三條邊的長(zhǎng)度。這種計(jì)算方式可以使用函數(shù)來(lái)表示。length(a, b)=√a2+b2 就是具體的計(jì)算方式。這樣的計(jì)算方式與現(xiàn)實(shí)中的實(shí)體沒(méi)有關(guān)聯(lián)。

基于計(jì)算的抽象方式可以進(jìn)一步提高代碼的復(fù)用性。在一個(gè)學(xué)生信息管理系統(tǒng)中，可能會(huì)需要找到一個(gè)班級(jí)的某門課程的最高分?jǐn)?shù)；在一個(gè)電子商務(wù)系統(tǒng)中，也可能會(huì)需要計(jì)算一個(gè)訂單的總金額?？此骑L(fēng)馬牛不相及的兩件事情，其實(shí)都包含了同樣的計(jì)算在里面。也就是對(duì)一個(gè)可迭代的對(duì)象進(jìn)行遍歷，同時(shí)在遍歷的過(guò)程中執(zhí)行自定義的操作。在計(jì)算最高分?jǐn)?shù)的場(chǎng)景中，在遍歷的同時(shí)需要保存當(dāng)前已知最高分?jǐn)?shù)，并在遍歷過(guò)程中更新該值；在計(jì)算訂單總金額的場(chǎng)景中，在遍歷的同時(shí)需要保存當(dāng)前已累積的金額，并在遍歷過(guò)程中更新該值。如果用 Java 代碼來(lái)實(shí)現(xiàn)，可以很容易寫(xiě)出如下兩段代碼。清單 1 計(jì)算學(xué)生的最高分?jǐn)?shù)。

清單 1. 計(jì)算學(xué)生的最高分?jǐn)?shù)的代碼

int maxMark = 0;

for (Student student : students) {

? if (student.getMark() > maxMark) {

? ? maxMark = student.getMark();

? }

}

清單 2 計(jì)算訂單的總金額。

清單 2. 計(jì)算訂單的總金額的代碼

BigDecimal total = BigDecimal.ZERO;

for (LineItem item : order.getLineItems()) {

? total = total.add(item.getPrice().multiply(new BigDecimal(item.getCount())));

}

在面向?qū)ο缶幊痰膶?shí)現(xiàn)中，這兩段代碼會(huì)分別添加到課程和訂單所對(duì)應(yīng)的類的某個(gè)方法中。課程對(duì)應(yīng)的類 Course 會(huì)有一個(gè)方法叫 getMaxMark，而訂單對(duì)應(yīng)的類 Order 會(huì)有一個(gè)方法叫 getTotal。盡管在實(shí)現(xiàn)上存在很多相似性和重復(fù)代碼，由于課程和訂單是兩個(gè)完全不相關(guān)的概念，并沒(méi)有辦法通過(guò)面向?qū)ο笾械睦^承或組合機(jī)制來(lái)提高代碼復(fù)用和減少重復(fù)。而函數(shù)式編程可以很好地解決這個(gè)問(wèn)題。

我們來(lái)進(jìn)一步看一下清單 1 和清單 2 中的代碼，嘗試提取其中的計(jì)算模式。該計(jì)算模式由 3 個(gè)部分組成：

保存計(jì)算結(jié)果的狀態(tài)，有初始值。

遍歷操作。

遍歷時(shí)進(jìn)行的計(jì)算，更新保存計(jì)算結(jié)果的狀態(tài)值。

把這 3 個(gè)元素提取出來(lái)，用偽代碼表示，就得到了清單 3 中用函數(shù)表示的計(jì)算模式。iterable 表示被迭代的對(duì)象，updateValue 是遍歷時(shí)進(jìn)行的計(jì)算，initialValue 是初始值。

清單 3. 計(jì)算模式的偽代碼

function(iterable, updateValue, initialValue) {

? value = initialValue

? loop(iterable) {

? ? ? value = updateValue(value, currentValue)

? }

? return value

}

了解函數(shù)式編程的讀者應(yīng)該已經(jīng)看出來(lái)了，這就是常用的 reduce 函數(shù)。使用 reduce 對(duì)清單 1 和清單 2 進(jìn)行改寫(xiě)，可以得到清單 4 中的兩段新的代碼。

清單 4. 使用 reduce 函數(shù)改寫(xiě)代碼

reduce(students, (mark, student) -> {

? return Math.max(student.getMark(), mark);

}, 0);

reduce(order.lineItems, (total, item) -> {

? return total.add(item.getPrice().multiply(new

BigDecimal(item.getCount())))

}, BigDecimal.ZERO);

函數(shù)類型與高階函數(shù)

對(duì)函數(shù)式編程支持程度高低的一個(gè)重要特征是函數(shù)是否作為編程語(yǔ)言的一等公民出現(xiàn)，也就是編程語(yǔ)言是否有內(nèi)置的結(jié)構(gòu)來(lái)表示函數(shù)。作為面向?qū)ο蟮木幊陶Z(yǔ)言，Java 中使用接口來(lái)表示函數(shù)。直到 Java 8，Java 才提供了內(nèi)置標(biāo)準(zhǔn) API 來(lái)表示函數(shù)，也就是 java.util.function 包。Function<T, R> 表示接受一個(gè)參數(shù)的函數(shù)，輸入類型為 T，輸出類型為 R。Function 接口只包含一個(gè)抽象方法 R apply(T t)，也就是在類型為 T 的輸入 t 上應(yīng)用該函數(shù)，得到類型為 R 的輸出。除了接受一個(gè)參數(shù)的 Function 之外，還有接受兩個(gè)參數(shù)的接口 BiFunction<T, U, R>，T 和 U 分別是兩個(gè)參數(shù)的類型，R 是輸出類型。BiFunction 接口的抽象方法為 R apply(T t, U u)。超過(guò) 2 個(gè)參數(shù)的函數(shù)在 Java 標(biāo)準(zhǔn)庫(kù)中并沒(méi)有定義。如果函數(shù)需要 3 個(gè)或更多的參數(shù)，可以使用第三方庫(kù)，如 Vavr 中的 Function0 到 Function8。

除了 Function 和 BiFunction 之外，Java 標(biāo)準(zhǔn)庫(kù)還提供了幾種特殊類型的函數(shù)：

Consumer<T>：接受一個(gè)輸入，沒(méi)有輸出。抽象方法為 void accept(T t)。

Supplier<T>：沒(méi)有輸入，一個(gè)輸出。抽象方法為 T get()。

Predicate<T>：接受一個(gè)輸入，輸出為 boolean 類型。抽象方法為 boolean test(T t)。

UnaryOperator<T>：接受一個(gè)輸入，輸出的類型與輸入相同，相當(dāng)于 Function<T, T>。

BinaryOperator<T>：接受兩個(gè)類型相同的輸入，輸出的類型與輸入相同，相當(dāng)于 BiFunction<T,T,T>。

BiPredicate<T, U>：接受兩個(gè)輸入，輸出為 boolean 類型。抽象方法為 boolean test(T t, U u)。

在本系列的第一篇文章中介紹 λ 演算時(shí)，提到了高階函數(shù)的概念。λ 項(xiàng)在定義時(shí)就支持以 λ 項(xiàng)進(jìn)行抽象和應(yīng)用。具體到實(shí)際的函數(shù)來(lái)說(shuō)，高階函數(shù)以其他函數(shù)作為輸入，或產(chǎn)生其他函數(shù)作為輸出。高階函數(shù)使得函數(shù)的組合成為可能，更有利于函數(shù)的復(fù)用。熟悉面向?qū)ο蟮淖x者對(duì)于對(duì)象的組合應(yīng)該不陌生。在劃分對(duì)象的職責(zé)時(shí)，組合被認(rèn)為是優(yōu)于繼承的一種方式。在使用對(duì)象組合時(shí)，每個(gè)對(duì)象所對(duì)應(yīng)的職責(zé)單一。多個(gè)對(duì)象通過(guò)組合的方式來(lái)完成復(fù)雜的行為。函數(shù)的組合類似對(duì)象的組合。上一節(jié)中提到的 reduce 就是一個(gè)高階函數(shù)的示例，其參數(shù) updateValue 也是一個(gè)函數(shù)。通過(guò)組合，reduce 把一部分邏輯代理給了作為其輸入的函數(shù) updateValue。不同的函數(shù)的嵌套層次可以很多，完成復(fù)雜的組合。

在 Java 中，可以使用函數(shù)類型來(lái)定義高階函數(shù)。上述函數(shù)接口都可以作為方法的參數(shù)和返回值。Java 標(biāo)準(zhǔn) API 已經(jīng)大量使用了這樣的方式。比如 Iterable 的 forEach 方法就接受一個(gè) Consumer 類型的參數(shù)。

在清單 5 中，notEqual 返回值是一個(gè) Predicate 對(duì)象，并使用在 Stream 的 filter 方法中。代碼運(yùn)行的輸出結(jié)果為 2 和 3。

清單 5. 高階函數(shù)示例

public class HighOrderFunctions {

? ? private static <T> Predicate<T> notEqual(T t) {

? ? ? ? return (v) -> !Objects.equals(v, t);

? ? }

?

? ? public static void main(String[] args) {

? ? ? List.of(1, 2, 3)

? ? ? ? ? .stream()

? ? ? ? ? .filter(notEqual(1))

? ? ? ? ? .forEach(System.out::println);

? ? }

}

部分函數(shù)

部分函數(shù)（partial function）是指僅有部分輸入?yún)?shù)被綁定了實(shí)際值的函數(shù)。清單 6 中的函數(shù) f(a, b, c) = a + b +c 有 3 個(gè)參數(shù) a、b 和 c。正常情況下調(diào)用該函數(shù)需要提供全部 3 個(gè)參數(shù)的值。如果只提供了部分參數(shù)的值，如只提供了 a 值，就得到了一個(gè)部分函數(shù)，其中參數(shù) a 被綁定成了給定值。假設(shè)給定的參數(shù) a 的值是 1，那新的部分函數(shù)的定義是 fa(b, c) = 1 + b + c。由于 a 的實(shí)際值可以有無(wú)窮多，也有對(duì)應(yīng)的無(wú)窮多種可能的部分函數(shù)。除了只對(duì) a 綁定值之外，還可以綁定參數(shù) b 和 c 的值。

清單 6. 部分函數(shù)示例

function f(a, b, c) {

? return a + b + c;

}

?

function fa(b, c) {

? return f(1, b, c);

}

部分函數(shù)可以用來(lái)為函數(shù)提供快捷方式，也就是預(yù)先綁定一些常用的參數(shù)值。比如函數(shù) add(a, b) = a + b 用來(lái)對(duì) 2 個(gè)參數(shù)進(jìn)行相加操作?？梢栽?add 基礎(chǔ)上創(chuàng)建一個(gè)部分函數(shù) increase，把參數(shù) b 的值綁定為 1。increase 相當(dāng)于進(jìn)行加 1 操作。同樣的，把參數(shù)值 b 綁定為 -1 可以得到函數(shù) decrease。

Java 標(biāo)準(zhǔn)庫(kù)并沒(méi)有提供對(duì)部分函數(shù)的支持，而且由于只提供了 Function 和 BiFunction，部分函數(shù)只對(duì) BiFunction 有意義。不過(guò)我們可以自己實(shí)現(xiàn)部分函數(shù)。部分函數(shù)在綁定參數(shù)時(shí)有兩種方式：一種是按照從左到右的順序綁定參數(shù)，另外一種是按照從右到左的順序綁定參數(shù)。這兩個(gè)方式分別對(duì)應(yīng)于 清單 7 中的 partialLeft 和 partialRight 方法。這兩個(gè)方法把一個(gè) BiFunction 轉(zhuǎn)換成一個(gè) Function。

清單 7. 部分函數(shù)的 Java 實(shí)現(xiàn)

public class PartialFunctions {

? private static? <T, U, R> Function<U, R> partialLeft(BiFunction<T,

U, R> biFunction, T t) {

? return (u) -> biFunction.apply(t, u);

? }

?

? private static? <T, U, R> Function<T, R> partialRight(BiFunction<T,

U, R> biFunction, U u) {

? return (t) -> biFunction.apply(t, u);

? }

?

?

? public static void main(String[] args) {

? ? BiFunction<Integer, Integer, Integer> biFunction = (v1, v2) -> v1

- v2;

? ? Function<Integer, Integer> subtractFrom10 =

partialLeft(biFunction, 10);

? ? Function<Integer, Integer> subtractBy10 = partialRight(biFunction,

10);

? ? System.out.println(subtractFrom10.apply(5)); // 5

? ? System.out.println(subtractBy10.apply(5));? // -5

? }

}

柯里化

柯里化（currying）是與λ演算相關(guān)的重要概念。通過(guò)柯里化，可以把有多個(gè)輸入的函數(shù)轉(zhuǎn)換成只有一個(gè)輸入的函數(shù)，從而可以在λ演算中來(lái)表示?？吕锘拿Q來(lái)源于數(shù)學(xué)家 Haskell Curry。Haskell Curry 是一位傳奇性的人物，以他的名字命令了 3 種編程語(yǔ)言，Haskell、Brook 和 Curry?？吕锘前延卸鄠€(gè)輸入?yún)?shù)的求值過(guò)程，轉(zhuǎn)換成多個(gè)只包含一個(gè)參數(shù)的函數(shù)的求值過(guò)程。對(duì)于清單 6 的函數(shù) f(a, b, c)，在柯里化之后轉(zhuǎn)換成函數(shù) g，則對(duì)應(yīng)的調(diào)用方式是 g(a)(b)(c)。函數(shù) (x, y) -> x + y 經(jīng)過(guò)柯里化之后的結(jié)果是 x -> (y -> x + y)。

柯里化與部分函數(shù)存在一定的關(guān)聯(lián)，但兩者是有區(qū)別的。部分函數(shù)的求值結(jié)果永遠(yuǎn)是實(shí)際的函數(shù)調(diào)用結(jié)果；而柯里化函數(shù)的求值結(jié)果則可能是另外一個(gè)函數(shù)。以清單 6 的部分函數(shù) fa 為例，每次調(diào)用 fa 時(shí)都必須提供剩余的 2 個(gè)參數(shù)。求值的結(jié)果都是具體的值；而調(diào)用柯里化之后的函數(shù) g(a) 得到的是另外的一個(gè)函數(shù)。只有通過(guò)遞歸的方式依次求值之后，才能得到最終的結(jié)果。

閉包

閉包（closure）是函數(shù)式編程相關(guān)的一個(gè)重要概念，也是很多開(kāi)發(fā)人員比較難以理解的概念。很多編程語(yǔ)言都有閉包或類似的概念。

在上一篇文章介紹 λ 演算的時(shí)候提到過(guò) λ 項(xiàng)的自由變量和綁定變量，如 λx.x+y 中的 y 就是自由變量。在對(duì)λ項(xiàng)求值時(shí)，需要一種方式可以獲取到自由變量的實(shí)際值。由于自由變量不在輸入中，其實(shí)際值只能來(lái)自于執(zhí)行時(shí)的上下文環(huán)境。實(shí)際上，閉包的概念來(lái)源于 1960 年代對(duì) λ 演算中表達(dá)式求值方式的研究。

閉包的概念與高階函數(shù)密切相關(guān)。在很多編程語(yǔ)言中，函數(shù)都是一等公民，也就是存在語(yǔ)言級(jí)別的結(jié)構(gòu)來(lái)表示函數(shù)。比如 Python 中就有函數(shù)類型，JavaScript 中有 function 關(guān)鍵詞來(lái)創(chuàng)建函數(shù)。對(duì)于這樣的語(yǔ)言，函數(shù)可以作為其他函數(shù)的參數(shù)，也可以作為其他函數(shù)的返回值。當(dāng)一個(gè)函數(shù)作為返回值，并且該函數(shù)內(nèi)部使用了出現(xiàn)在其所在函數(shù)的詞法域（lexical scope）的自由變量時(shí)，就創(chuàng)建了一個(gè)閉包。我們首先通過(guò)一段簡(jiǎn)單的 JavaScript 代碼來(lái)直觀地了解閉包。

清單 8 中的函數(shù) idGenerator 用來(lái)創(chuàng)建簡(jiǎn)單的遞增式的 ID 生成器。參數(shù) initialValue 是遞增的初始值。返回值是另外一個(gè)函數(shù)，在調(diào)用時(shí)會(huì)返回并遞增 count 的值。這段代碼就用到了閉包。idGenerator 返回的函數(shù)中使用了其所在函數(shù)的詞法域中的自由變量 count。count 不在返回的函數(shù)中定義，而是來(lái)自包含該函數(shù)的詞法域。在實(shí)際調(diào)用中，雖然 idGenerator 函數(shù)的執(zhí)行已經(jīng)結(jié)束，其返回的函數(shù) genId 卻仍然可以訪問(wèn) idGenerator 詞法域中的變量 count。這是由閉包的上下文環(huán)境提供的。

清單 8. JavaScript 中的閉包示例

function idGenerator(initialValue) {

let count = initialValue;

return function() {

? ? ? return count++;

};

}

?

let genId = idGenerator(0);

genId(); // 0

genId(); // 1

從上述簡(jiǎn)單的例子中，可以得出來(lái)構(gòu)成閉包的兩個(gè)要件：

一個(gè)函數(shù)

負(fù)責(zé)綁定自由變量的上下文環(huán)境

函數(shù)是閉包對(duì)外的呈現(xiàn)部分。在閉包創(chuàng)建之后，閉包的存在與否對(duì)函數(shù)的使用者是透明的。比如清單 8 中的 genId 函數(shù)，使用者只需要調(diào)用即可，并不需要了解背后是否有閉包的存在。上下文環(huán)境則是閉包背后的實(shí)現(xiàn)機(jī)制，由編程語(yǔ)言的運(yùn)行時(shí)環(huán)境來(lái)提供。該上下文環(huán)境需要為函數(shù)創(chuàng)建一個(gè)映射，把函數(shù)中的每個(gè)自由變量與閉包創(chuàng)建時(shí)的對(duì)應(yīng)值關(guān)聯(lián)起來(lái)，使得閉包可以繼續(xù)訪問(wèn)這些值。在 idGenerator 的例子中，上下文環(huán)境負(fù)責(zé)關(guān)聯(lián)變量 count 的值，該變量可以在返回的函數(shù)中繼續(xù)訪問(wèn)和修改。

從上述兩個(gè)要件也可以得出閉包這個(gè)名字的由來(lái)。閉包是用來(lái)封閉自由變量的，適合用來(lái)實(shí)現(xiàn)內(nèi)部狀態(tài)。比如清單 8 中的 count 是無(wú)法被外部所訪問(wèn)的。一旦 idGenerator 返回之后，唯一的引用就來(lái)自于所返回的函數(shù)。在 JavaScript 中，閉包可以用來(lái)實(shí)現(xiàn)真正意義上的私有變量。

從閉包的使用方式可以得知，閉包的生命周期長(zhǎng)于創(chuàng)建它的函數(shù)。因此，自由變量不能在堆棧上分配；否則一旦函數(shù)退出，自由變量就無(wú)法繼續(xù)訪問(wèn)。因此，閉包所訪問(wèn)的自由變量必須在堆上分配。也正因?yàn)槿绱耍С珠]包的編程語(yǔ)言都有垃圾回收機(jī)制，來(lái)保證閉包所訪問(wèn)的變量可以被正確地釋放。同樣，不正確地使用閉包可能造成潛在的內(nèi)存泄漏。

閉包的一個(gè)重要特性是其中的自由變量所綁定的是閉包創(chuàng)建時(shí)的值，而不是變量的當(dāng)前值。清單 9 是一個(gè)簡(jiǎn)單的 HTML 頁(yè)面的代碼，其中有 3 個(gè)按鈕。用瀏覽器打開(kāi)該頁(yè)面時(shí)，點(diǎn)擊 3 個(gè)按鈕會(huì)發(fā)現(xiàn)，所彈出的值全部都是 3。這是因?yàn)楫?dāng)點(diǎn)擊按鈕時(shí)，循環(huán)已經(jīng)執(zhí)行完成，i 的當(dāng)前值已經(jīng)是 3。所以按鈕的 click 事件處理函數(shù)所得到是 i 的當(dāng)前值 3。

清單 9. 閉包綁定值的演示頁(yè)面

<!DOCTYPE html>

<htmllang="en">

<head>

? <title>Test</title>

</head>

<body>

? <button>Button 1</button>

? <button>Button 2</button>

? <button>Button 3</button>

</body>

<script>

? varbuttons = document.getElementsByTagName("button");

? for(vari = 0; i < buttons.length; i++) {? ? ? ?

? ? buttons[i].addEventListener("click", function() {

? ? ? alert(i);? ? ? ? ? ?

? ? });

? }

</script>

</html>

如果把 JavaScript 代碼改成清單 10 所示，就可以得到所期望的結(jié)果。我們創(chuàng)建了一個(gè)匿名函數(shù)并馬上調(diào)用該函數(shù)來(lái)返回真正的事件處理函數(shù)。處理函數(shù)中訪問(wèn)的變量 i 現(xiàn)在成為了閉包的自由變量，因此 i 的值被綁定到閉包創(chuàng)建時(shí)的值，也就是每個(gè)循環(huán)執(zhí)行過(guò)程中的實(shí)際值。

清單 10. 使用閉包解決綁定值的問(wèn)題

var buttons = document.getElementsByTagName("button");

for (var i = 0; i < buttons.length; i++) {? ? ? ?

? buttons[i].addEventListener("click", function(i) {

? ? ? return function() {

? ? ? ? alert(i);? ? ? ? ? ?

? ? ? }

? ? }(i));

}

在 Java 中有與閉包類似的概念，那就是匿名內(nèi)部類。在匿名內(nèi)部類中，可以訪問(wèn)詞法域中聲明為 final 的變量。不是 final 的變量無(wú)法被訪問(wèn)，會(huì)出現(xiàn)編譯錯(cuò)誤。匿名內(nèi)部類提供了一種方式來(lái)共享局部變量。不過(guò)并不能對(duì)該變量的引用進(jìn)行修改。在清單? 11 中，變量 latch 被兩個(gè)匿名內(nèi)部類所使用。

清單 11. Java 中的匿名內(nèi)部類

public class InnerClasses {

?

? public static void main(String[] args) {

? ? final CountDownLatch latch = new CountDownLatch(1);

?

? ? final Future<?> task1 = ForkJoinPool.commonPool().submit(() -> {

? ? ? try {

? ? ? ? Thread.sleep(ThreadLocalRandom.current().nextInt(2000));

? ? ? } catch (InterruptedException e) {

? ? ? ? e.printStackTrace();

? ? ? } finally {

? ? ? ? latch.countDown();

? ? ? }

? ? });

?

? ? final Future<?> task2 = ForkJoinPool.commonPool().submit(() -> {

? ? ? final long start = System.currentTimeMillis();

? ? ? try {

? ? ? ? latch.await();

? ? ? } catch (InterruptedException e) {

? ? ? ? e.printStackTrace();

? ? ? } finally {

? ? ? ? System.out.println("Done after " + (System.currentTimeMillis()

- start) + "ms");

? ? ? }

? ? });

?

? ? try {

? ? ? task1.get();

? ? ? task2.get();

? ? } catch (InterruptedException | ExecutionException e) {

? ? ? e.printStackTrace();

? ? }

? }

}

可以被共享的變量必須聲明為 final。這個(gè)限制只對(duì)變量引用有效。只要對(duì)象本身是可變的，仍然可以修改該對(duì)象的內(nèi)容。比如一個(gè) List 類型的變量，雖然對(duì)它的引用是 final 的，仍然可以通過(guò)其方法來(lái)修改 List 內(nèi)部的值。

遞歸

遞歸（recursion）是編程中的一個(gè)重要概念。很多編程語(yǔ)言，不僅限于函數(shù)式編程語(yǔ)言，都有遞歸這樣的結(jié)構(gòu)。從代碼上來(lái)說(shuō)，遞歸允許一個(gè)函數(shù)在其內(nèi)部調(diào)用該函數(shù)自身。有些函數(shù)式編程語(yǔ)言并沒(méi)有循環(huán)這樣的結(jié)構(gòu)，而是通過(guò)遞歸來(lái)實(shí)現(xiàn)循環(huán)。遞歸和循環(huán)在表達(dá)能力上是相同的，只不過(guò)命令式編程語(yǔ)言偏向于使用循環(huán)，而函數(shù)式編程語(yǔ)言偏向于使用遞歸。遞歸的優(yōu)勢(shì)在于天然適合于那些需要用分治法（divide and conquer）解決的問(wèn)題，把一個(gè)大問(wèn)題劃分成小問(wèn)題，以遞歸的方式解決。經(jīng)典的通過(guò)遞歸解決的問(wèn)題包括階乘計(jì)算、計(jì)算最大公約數(shù)的歐幾里德算法、漢諾塔、二分查找、樹(shù)的深度優(yōu)先遍歷和快速排序等。

遞歸分為單遞歸和多遞歸。單遞歸只包含一個(gè)對(duì)自身的引用；而多遞歸則包含多個(gè)對(duì)自身的引用。單遞歸的例子包括列表遍歷和計(jì)算階乘等；多遞歸的例子包括樹(shù)遍歷等。在具體的編程實(shí)踐中，單遞歸可以比較容易改寫(xiě)成使用循環(huán)的形式，而多遞歸則一般保持遞歸的形式。清單 12 給出了 JavaScript 實(shí)現(xiàn)的計(jì)算階乘的遞歸寫(xiě)法。

清單 12. 遞歸方式計(jì)算階乘

int fact(n) {

? if (n === 0) {

? ? ? return 1;

? } else {

? ? ? return n * fact(n - 1);

? }

}

而下面的清單 13 則是 JavaScript 實(shí)現(xiàn)的使用循環(huán)的寫(xiě)法。

清單 13. 循環(huán)方式計(jì)算階乘

int fact_i(n) {

? let result = 1;

? for (let i = n; i > 0; i--) {

? ? result = result * i;

? }

? return result;

}

有一種特殊的遞歸方式叫尾遞歸。如果函數(shù)中的遞歸調(diào)用都是尾調(diào)用，則該函數(shù)是尾遞歸函數(shù)。尾遞歸的特性使得遞歸調(diào)用不需要額外的空間，執(zhí)行起來(lái)也更快。不少編程語(yǔ)言會(huì)自動(dòng)對(duì)尾遞歸進(jìn)行優(yōu)化。

下面我們以歐幾里德算法來(lái)說(shuō)明一下尾遞歸。該算法的 Java 實(shí)現(xiàn)比較簡(jiǎn)單，如清單 14 所示。函數(shù) gcd 的尾調(diào)用是遞歸調(diào)用 gcd 本身。

清單 14. 尾遞歸的方式實(shí)現(xiàn)歐幾里德算法

int gcd(x, y) {

? if (y == 0) {

? ? ? return x;

? }

? return gcd(y, x % y);

}

尾遞歸的特性在于實(shí)現(xiàn)時(shí)可以復(fù)用函數(shù)的當(dāng)前調(diào)用棧的幀。當(dāng)函數(shù)執(zhí)行到尾調(diào)用時(shí)，只需要簡(jiǎn)單的 goto 語(yǔ)句跳轉(zhuǎn)到函數(shù)開(kāi)頭并更新參數(shù)的值即可。相對(duì)于循環(huán)，遞歸的一個(gè)大的問(wèn)題是層次過(guò)深的函數(shù)調(diào)用棧導(dǎo)致占用內(nèi)存空間過(guò)大。對(duì)尾遞歸的優(yōu)化，使得遞歸只需要使用與循環(huán)相似大小的內(nèi)存空間。

記憶化

記憶化（memoization）也是函數(shù)式編程中的重要概念，其核心思想是以空間換時(shí)間，提高函數(shù)的執(zhí)行性能，尤其是使用遞歸來(lái)實(shí)現(xiàn)的函數(shù)。使用記憶化要求函數(shù)具有引用透明性，從而可以把函數(shù)的調(diào)用結(jié)果與調(diào)用時(shí)的參數(shù)關(guān)聯(lián)起來(lái)。通常是做法是在函數(shù)內(nèi)部維護(hù)一個(gè)查找表。查找表的鍵是輸入的參數(shù)，對(duì)應(yīng)的值是函數(shù)的返回結(jié)果。在每次調(diào)用時(shí)，首先檢查內(nèi)部的查找表，如果存在與輸入?yún)?shù)對(duì)應(yīng)的值，則直接返回已經(jīng)記錄的值。否則的話，先進(jìn)行計(jì)算，再用得到的值更新查找表。通過(guò)這樣的方式可以避免重復(fù)的計(jì)算。

最典型的展示記憶化應(yīng)用的例子是計(jì)算斐波那契數(shù)列 (Fibonacci sequence)。該數(shù)列的表達(dá)式是 F[n]=F[n-1]+F[n-2](n>=2,F[0]=0,F[1]=1)。清單 15 是斐波那契數(shù)列的一個(gè)簡(jiǎn)單實(shí)現(xiàn)，直接體現(xiàn)了斐波那契數(shù)列的定義。函數(shù) fib 可以正確完成數(shù)列的計(jì)算，但是性能極差。當(dāng)輸入 n 的值稍微大一些的時(shí)候，計(jì)算速度就非常之慢，甚至?xí)霈F(xiàn)無(wú)法完成的情況。這是因?yàn)槔锩嬗刑嗟闹貜?fù)計(jì)算。比如在計(jì)算 fib(4) 的時(shí)候，會(huì)計(jì)算 fib(3) 和 fib(2)。在計(jì)算 fib(3) 的時(shí)候，也會(huì)計(jì)算 fib(2)。由于 fib 函數(shù)的返回值僅由參數(shù) n 決定，當(dāng)?shù)谝淮蔚贸瞿硞€(gè) n 對(duì)應(yīng)的結(jié)果之后，就可以使用查找表把結(jié)果保存下來(lái)。這里需要使用 BigInteger 來(lái)表示值，因?yàn)?fib 函數(shù)的值已經(jīng)超出了 Long 所能表示的范圍。

清單 15. 計(jì)算斐波那契數(shù)列的樸素實(shí)現(xiàn)

import java.math.BigInteger;

public class Fib {

public static void main(String[] args) {

? System.out.println(fib(40));

}

private static BigInteger fib(int n) {

? if (n == 0) {

? ? return BigInteger.ZERO;

? } else if (n == 1) {

? ? return BigInteger.ONE;

? }

? return fib(n - 1).add(fib(n - 2));

}

}

清單 16 是使用記憶化之后的計(jì)算類 FibMemoized。已經(jīng)計(jì)算的值保存在查找表 lookupTable 中。每次計(jì)算之前，首先查看查找表中是否有值。改進(jìn)后的函數(shù)的性能有了數(shù)量級(jí)的提升，即便是 fib(100) 也能很快完成。

清單 16. 使用記憶化的斐波那契數(shù)列計(jì)算

import java.math.BigInteger;

import java.util.HashMap;

import java.util.Map;

public class FibMemoized {

public static void main(String[] args) {

? System.out.println(fib(100));

}

private static Map<Integer, BigInteger> lookupTable = new

HashMap<>();

static {

? lookupTable.put(0, BigInteger.ZERO);

? lookupTable.put(1, BigInteger.ONE);

}

private static BigInteger fib(int n) {

? if (lookupTable.containsKey(n)) {

? ? return lookupTable.get(n);

? } else {

? ? BigInteger result = fib(n - 1).add(fib(n - 2));

? ? lookupTable.put(n, result);

? ? return result;

? }

}

}

很多函數(shù)式編程庫(kù)都提供了對(duì)記憶化的支持，會(huì)在本系列后續(xù)的文章中介紹。

總結(jié)

本文對(duì)函數(shù)式編程相關(guān)的一些重要概念做了系統(tǒng)性介紹。理解這些概念可以為應(yīng)用函數(shù)式編程實(shí)踐打下良好的基礎(chǔ)。本文首先介紹了函數(shù)式編程范式的意義，接著介紹了函數(shù)類型與高階函數(shù)、部分函數(shù)、柯里化、閉包、遞歸和記憶化等概念。下一篇文章將介紹 Java 8 所引入的 Lambda 表達(dá)式和流處理。

參考資源

了解更多關(guān)于柯里化的內(nèi)容。

了解更多關(guān)于遞歸的內(nèi)容。

了解更多關(guān)于記憶化的內(nèi)容。