前言

在這一期的文章中，我將繼續(xù)介紹 Either，使用它構(gòu)建樹(shù)形結(jié)構(gòu)，該結(jié)構(gòu)允許我模擬 Scala 的模式匹配來(lái)構(gòu)建遍歷方法。

在 Java 中使用泛型數(shù)據(jù)，Either 會(huì)成為接收兩種類型之一的單一數(shù)據(jù)結(jié)構(gòu)，這兩種類型保存在 left 和 right 部分中。

在上一期文章的羅馬數(shù)字解析器示例中，Either 保存了 Exception（左側(cè)）或 Integer（右側(cè)），如圖 1 所示：

圖 1. Either 抽象保存了兩種類型的其中之一

在本示例中，Either以如下的方式被填充：

Either<Exception, Integer> result = RomanNumeralParser.parseNumber("XLII");

Scala 模式匹配

Scala 的眾多出色功能之一就是能夠使用 模式匹配 進(jìn)行調(diào)度（參閱 參考資料）。與描述相比，演示更簡(jiǎn)單一些，因此我們會(huì)考慮清單 1 中的函數(shù)，將數(shù)字分?jǐn)?shù)轉(zhuǎn)換為字母分?jǐn)?shù)：

清單 1. 使用 Scala 模式匹配根據(jù)分?jǐn)?shù)調(diào)度字母分?jǐn)?shù)

val VALID_GRADES = Set("A", "B", "C", "D", "F")
def letterGrade(value: Any) : String = value match {
case x:Int if (90 to 100).contains(x) => "A"
case x:Int if (80 to 90).contains(x) => "B"
case x:Int if (70 to 80).contains(x) => "C"
case x:Int if (60 to 70).contains(x) => "D"
case x:Int if (0 to 60).contains(x) => "F"
case x:String if VALID_GRADES(x.toUpperCase) => x.toUpperCase
}
printf("Amy scores %d and receives %s\n", 91, letterGrade(91))
printf("Bob scores %d and receives %s\n", 72, letterGrade(72))
printf("Sam never showed for class, scored %d, and received %s\n", 
44, letterGrade(44))
printf("Roy transfered and already had %s, which translated as %s\n",
"B", letterGrade("B"))

在 清單 1 中，函數(shù)的整個(gè)正文由應(yīng)用于 value 的 match 構(gòu)成。對(duì)于每個(gè)選項(xiàng)，模式防護(hù) 允許我根據(jù)除參數(shù)類型以外的條件篩選匹配內(nèi)容。這種語(yǔ)法的優(yōu)勢(shì)是一個(gè)干凈的選項(xiàng)分區(qū)，而不是一系列復(fù)雜的 if 語(yǔ)句。

模式匹配與 Scala 的 case 類一同工作，該類是具有特殊屬性的類 （包括執(zhí)行模式匹配的能力），以消除決策序列?？紤]匹配顏色組合，如清單 2 所示：

清單 2. 在 Scala 中匹配 case 類

class Color(val red:Int, val green:Int, val blue:Int)
case class Red(r:Int) extends Color(r, 0, 0)
case class Green(g:Int) extends Color(0, g, 0)
case class Blue(b:Int) extends Color(0, 0, b)
def printColor(c:Color) = c match {
case Red(v) => println("Red: " + v)
case Green(v) => println("Green: " + v)
case Blue(v) => println("Blue: " + v)
case col:Color => {
print("R: " + col.red + ", ")
print("G: " + col.green + ", ")
println("B: " + col.blue)
}
case null => println("invalid color")
}

在 清單 2 中，我創(chuàng)建了一個(gè)基本 Color 類，然后與 case 類一樣，創(chuàng)建了一個(gè)特殊的單一顏色版本。當(dāng)確定將哪種顏色傳遞給函數(shù)時(shí)，我使用了 match，根據(jù)所有可用選項(xiàng)進(jìn)行模式匹配，這些可用選項(xiàng)中包括最后一個(gè) case，它將處理 null。

Java 沒(méi)有提供模式匹配，因此它無(wú)法復(fù)制 Scala 的創(chuàng)建清晰可讀的調(diào)度代碼的能力。但是，通過(guò)結(jié)合使用泛型數(shù)據(jù)結(jié)構(gòu)和眾所周知的數(shù)據(jù)結(jié)構(gòu)，可以實(shí)現(xiàn)更加接近的能力，這又將我?guī)Щ亓?Either。

Either 樹(shù)

可以建模一個(gè)具有三個(gè)抽象的樹(shù)形數(shù)據(jù)結(jié)構(gòu)，如表 1 所示：

但是為了方便起見(jiàn)，我將在本例中使用來(lái)自 Functional Java 框架的一個(gè)類。從概念上講，Either 抽象擴(kuò)展到了所需的方面。例如，您可以考慮聲明 Either<Empty, Either<Leaf, Node>>，這將創(chuàng)建一個(gè)三部分的數(shù)據(jù)結(jié)構(gòu)，如圖 2 所示：

圖 2. Either<Empty, Either<Leaf, Node>> 的數(shù)據(jù)結(jié)構(gòu)

執(zhí)行了三個(gè)樹(shù)抽象的 Either 實(shí)現(xiàn)之后，我定義了樹(shù)，如清單 3 所示：

清單 3. 基于 Either 的樹(shù)

import fj.data.Either;
import static fj.data.Either.left;
import static fj.data.Either.right;
public abstract class Tree {
private Tree() {}
public abstract Either<Empty, Either<Leaf, Node>> toEither();
public static final class Empty extends Tree {
public Either<Empty, Either<Leaf, Node>> toEither() {
return left(this);
}
public Empty() {}
}
public static final class Leaf extends Tree {
public final int n;
public Either<Empty, Either<Leaf, Node>> toEither() {
return right(Either.<Leaf, Node>left(this));
}
public Leaf(int n) { this.n = n; }
}
public static final class Node extends Tree {
public final Tree left;
public final Tree right;
public Either<Empty, Either<Leaf, Node>> toEither() {
return right(Either.<Leaf, Node>right(this));
}
public Node(Tree left, Tree right) {
this.left = left;
this.right = right;
}
}
}

清單 3 中的抽象 Tree 類定義了三個(gè) final 具體類：Empty、Leaf 和 Node。從內(nèi)部講，Tree 類使用 3 個(gè)插槽的 Either，如 圖 2 所示，實(shí)現(xiàn)這樣一種規(guī)則，即最左側(cè)的插槽總是保存 Empty，中間插槽保存 Leaf，而最右側(cè)的插槽保存 Node。方法是：請(qǐng)求每個(gè)類都實(shí)現(xiàn) toEither() 方法，返回該類型相應(yīng)的 “插槽”。從傳統(tǒng)計(jì)算機(jī)科學(xué)方面講，數(shù)據(jù)結(jié)構(gòu)中的每個(gè) “單元” 都是一個(gè) union，旨在保存任意給定時(shí)間三種可能類型的其中一種類型。

考慮到此樹(shù)形結(jié)構(gòu)和其內(nèi)部結(jié)構(gòu)基于 <Either, <Left, Node>> 的事實(shí)，我可以通過(guò)模擬模式匹配來(lái)訪問(wèn)樹(shù)中的每個(gè)元素。

樹(shù)遍歷的模式匹配

Scala 的模式匹配鼓勵(lì)您思考離散情況。Functional Java 的 Either 實(shí)現(xiàn)中的 left() 和 right() 方法都實(shí)現(xiàn)了 Iterable 接口；這允許我編寫支持模式匹配的代碼來(lái)確定樹(shù)的深度，如清單 4 所示：

清單 4. 使用類似模式匹配的語(yǔ)法檢查樹(shù)的深度

static public int depth(Tree t) {
for (Empty e : t.toEither().left())
return 0;
for (Either<Leaf, Node> ln: t.toEither().right()) {
for (Leaf leaf : ln.left())
return 1;
for (Node node : ln.right())
return 1 + max(depth(node.left), depth(node.right));
}
throw new RuntimeException("Inexhaustible pattern match on tree");
}

清單 4 中的 depth() 方法是一個(gè)遞歸深度查找函數(shù)。因?yàn)槲业臉?shù)基于一個(gè)具體的數(shù)據(jù)結(jié)構(gòu)（<Either, <Left, Node>>），所以我可以將每個(gè) “插槽” 視為一個(gè)具體情況。如果單元為空，則樹(shù)枝沒(méi)有深度。如果單元為葉，則將它視為樹(shù)級(jí)別。如果單元為節(jié)點(diǎn)，那么我會(huì)知道應(yīng)該以遞歸方式搜索左側(cè)和右側(cè)，然后添加 1 進(jìn)行另一次遞歸。

我還可以使用相同的模式匹配語(yǔ)法來(lái)執(zhí)行樹(shù)的遞歸搜索，如清單 5 所示：

清單 5. 在樹(shù)中確定是否存在元素

static public boolean inTree(Tree t, int value) {
for (Empty e : t.toEither().left())
return false;
for (Either<Leaf, Node> ln: t.toEither().right()) {
for (Leaf leaf : ln.left())
return value == leaf.n;
for (Node node : ln.right())
return inTree(node.left, value) | inTree(node.right, value);
}
return false;
}

與之前一樣，我在數(shù)據(jù)結(jié)構(gòu)中為每個(gè)可能的 “插槽” 指定一個(gè) return 值。如果遇到一個(gè)空單元，則會(huì)返回 false；我的搜索會(huì)失敗。對(duì)于葉，我會(huì)檢查傳遞的值，如果它們匹配則返回 true。否則，在遇到節(jié)點(diǎn)時(shí)，我會(huì)遍歷樹(shù)，使用 |（非短路的 or 運(yùn)算符）來(lái)組合返回的布爾值。

要查看實(shí)際的樹(shù)創(chuàng)建和搜索，請(qǐng)考慮清單 6 中的單元測(cè)試：

清單 6. 測(cè)試樹(shù)可搜索性

@Test
public void more_elaborate_searchp_test() {
Tree t = new Node(new Node(new Node(new Node(
new Node(new Leaf(4),new Empty()), 
new Leaf(12)), new Leaf(55)), 
new Empty()), new Leaf(4));
assertTrue(inTree(t, 55));
assertTrue(inTree(t, 4));
assertTrue(inTree(t, 12));
assertFalse(inTree(t, 42));
}

在 清單 6 中，我構(gòu)建了樹(shù)，然后調(diào)查了是否存在元素。inTree() 方法返回 true，如果其中一個(gè)葉等于搜索值，并且 true 傳播了遞歸調(diào)用堆棧，這是因?yàn)?| ("or") 運(yùn)算符，如 清單 5 所示。

清單 5 中的示例確定了元素是否出現(xiàn)于樹(shù)中。更復(fù)雜的版本還會(huì)檢查出現(xiàn)的次數(shù)，如清單 7 所示：

清單 7. 查找在樹(shù)中出現(xiàn)的次數(shù)

static public int occurrencesIn(Tree t, int value) {
for (Empty e: t.toEither().left())
return 0;
for (Either<Leaf, Node> ln: t.toEither().right()) {
for (Leaf leaf : ln.left())
if (value == leaf.n) return 1;
for (Node node : ln.right())
return occurrencesIn(node.left, value) + occurrencesIn(node.right, value);
}
return 0;
}

在 清單 7 中，我為每個(gè)匹配的葉返回了 1，這使我可以計(jì)算樹(shù)中每個(gè)數(shù)字出現(xiàn)的次數(shù)。

清單 8 展示了復(fù)雜樹(shù)中 depth()、inTree() 和 occurrencesIn() 的測(cè)試：

清單 8. 在復(fù)雜樹(shù)中測(cè)試深度、存在狀況和出現(xiàn)次數(shù)

@Test
public void multi_branch_tree_test() {
Tree t = new Node(new Node(new Node(new Leaf(4),
new Node(new Leaf(1), new Node(
new Node(new Node(new Node(
new Node(new Node(new Leaf(10), new Leaf(0)),
new Leaf(22)), new Node(new Node(
new Node(new Leaf(4), new Empty()),
new Leaf(101)), new Leaf(555))),
new Leaf(201)), new Leaf(1000)),
new Leaf(4)))),
new Leaf(12)), new Leaf(27));
assertEquals(12, depth(t));
assertTrue(inTree(t, 555));
assertEquals(3, occurrencesIn(t, 4));
}

由于我對(duì)樹(shù)的內(nèi)部結(jié)構(gòu)應(yīng)用了正則性，因此我可以在遍歷期間分析樹(shù)，方法是思考每種情況，如元素類型所示。該語(yǔ)法盡管不像完全成熟的 Scala 模式匹配一樣強(qiáng)大，但是與 Scala 出乎意料的接近。

結(jié)束語(yǔ)

在這一期的文章中，我介紹了如何在樹(shù)遍歷期間，對(duì)啟用了 Scala 風(fēng)格的模式匹配應(yīng)用正則性，以及如何利用泛型 Iterable 的一些固有屬性、Functional Java 的 Either 類和其他一些元素來(lái)模擬強(qiáng)大的 Scala 功能。

以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。