通過實例學習Either 樹和模式匹配
前言
在這一期的文章中，我將繼續(xù)介紹 Either，使用它構(gòu)建樹形結(jié)構(gòu)，該結(jié)構(gòu)允許我模擬 Scala 的模式匹配來構(gòu)建遍歷方法。
在 Java 中使用泛型數(shù)據(jù)，Either 會成為接收兩種類型之一的單一數(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 的眾多出色功能之一就是能夠使用 模式匹配 進行調(diào)度（參閱 參考資料）。與描述相比，演示更簡單一些，因此我們會考慮清單 1 中的函數(shù)，將數(shù)字分數(shù)轉(zhuǎn)換為字母分數(shù)：
清單 1. 使用 Scala 模式匹配根據(jù)分數(shù)調(diào)度字母分數(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ù)的整個正文由應用于 value 的 match 構(gòu)成。對于每個選項，模式防護 允許我根據(jù)除參數(shù)類型以外的條件篩選匹配內(nèi)容。這種語法的優(yōu)勢是一個干凈的選項分區(qū)，而不是一系列復雜的 if 語句。
模式匹配與 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)建了一個基本 Color 類，然后與 case 類一樣，創(chuàng)建了一個特殊的單一顏色版本。當確定將哪種顏色傳遞給函數(shù)時，我使用了 match，根據(jù)所有可用選項進行模式匹配，這些可用選項中包括最后一個 case，它將處理 null。
Java 沒有提供模式匹配，因此它無法復制 Scala 的創(chuàng)建清晰可讀的調(diào)度代碼的能力。但是，通過結(jié)合使用泛型數(shù)據(jù)結(jié)構(gòu)和眾所周知的數(shù)據(jù)結(jié)構(gòu)，可以實現(xiàn)更加接近的能力，這又將我?guī)Щ亓?Either。
Either 樹
可以建模一個具有三個抽象的樹形數(shù)據(jù)結(jié)構(gòu)，如表 1 所示：
| Empty | 單元中不包含任何值 |
|---|---|
| Leaf | 單元中擁有一個特殊數(shù)據(jù)類型值 |
| Node | 指向其他 葉 或 節(jié)點 |
但是為了方便起見，我將在本例中使用來自 Functional Java 框架的一個類。從概念上講，Either 抽象擴展到了所需的方面。例如，您可以考慮聲明 Either<Empty, Either<Leaf, Node>>，這將創(chuàng)建一個三部分的數(shù)據(jù)結(jié)構(gòu)，如圖 2 所示：
圖 2. Either<Empty, Either<Leaf, Node>> 的數(shù)據(jù)結(jié)構(gòu)
執(zhí)行了三個樹抽象的 Either 實現(xiàn)之后，我定義了樹，如清單 3 所示：
清單 3. 基于 Either 的樹
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 類定義了三個 final 具體類：Empty、Leaf 和 Node。從內(nèi)部講，Tree 類使用 3 個插槽的 Either，如 圖 2 所示，實現(xiàn)這樣一種規(guī)則，即最左側(cè)的插槽總是保存 Empty，中間插槽保存 Leaf，而最右側(cè)的插槽保存 Node。方法是：請求每個類都實現(xiàn) toEither() 方法，返回該類型相應的 “插槽”。從傳統(tǒng)計算機科學方面講，數(shù)據(jù)結(jié)構(gòu)中的每個 “單元” 都是一個 union，旨在保存任意給定時間三種可能類型的其中一種類型。
考慮到此樹形結(jié)構(gòu)和其內(nèi)部結(jié)構(gòu)基于 <Either, <Left, Node>> 的事實，我可以通過模擬模式匹配來訪問樹中的每個元素。
樹遍歷的模式匹配
Scala 的模式匹配鼓勵您思考離散情況。Functional Java 的 Either 實現(xiàn)中的 left() 和 right() 方法都實現(xiàn)了 Iterable 接口；這允許我編寫支持模式匹配的代碼來確定樹的深度，如清單 4 所示：
清單 4. 使用類似模式匹配的語法檢查樹的深度
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() 方法是一個遞歸深度查找函數(shù)。因為我的樹基于一個具體的數(shù)據(jù)結(jié)構(gòu)（<Either, <Left, Node>>），所以我可以將每個 “插槽” 視為一個具體情況。如果單元為空，則樹枝沒有深度。如果單元為葉，則將它視為樹級別。如果單元為節(jié)點，那么我會知道應該以遞歸方式搜索左側(cè)和右側(cè)，然后添加 1 進行另一次遞歸。
我還可以使用相同的模式匹配語法來執(zhí)行樹的遞歸搜索，如清單 5 所示：
清單 5. 在樹中確定是否存在元素
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)中為每個可能的 “插槽” 指定一個 return 值。如果遇到一個空單元，則會返回 false；我的搜索會失敗。對于葉，我會檢查傳遞的值，如果它們匹配則返回 true。否則，在遇到節(jié)點時，我會遍歷樹，使用 |（非短路的 or 運算符）來組合返回的布爾值。
要查看實際的樹創(chuàng)建和搜索，請考慮清單 6 中的單元測試：
清單 6. 測試樹可搜索性
@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)建了樹，然后調(diào)查了是否存在元素。inTree() 方法返回 true，如果其中一個葉等于搜索值，并且 true 傳播了遞歸調(diào)用堆棧，這是因為 | ("or") 運算符，如 清單 5 所示。
清單 5 中的示例確定了元素是否出現(xiàn)于樹中。更復雜的版本還會檢查出現(xiàn)的次數(shù)，如清單 7 所示：
清單 7. 查找在樹中出現(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 中，我為每個匹配的葉返回了 1，這使我可以計算樹中每個數(shù)字出現(xiàn)的次數(shù)。
清單 8 展示了復雜樹中 depth()、inTree() 和 occurrencesIn() 的測試：
清單 8. 在復雜樹中測試深度、存在狀況和出現(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));
}
由于我對樹的內(nèi)部結(jié)構(gòu)應用了正則性，因此我可以在遍歷期間分析樹，方法是思考每種情況，如元素類型所示。該語法盡管不像完全成熟的 Scala 模式匹配一樣強大，但是與 Scala 出乎意料的接近。
結(jié)束語
在這一期的文章中，我介紹了如何在樹遍歷期間，對啟用了 Scala 風格的模式匹配應用正則性，以及如何利用泛型 Iterable 的一些固有屬性、Functional Java 的 Either 類和其他一些元素來模擬強大的 Scala 功能。
以上就是本文的全部內(nèi)容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。
SpringBoot集成支付寶沙箱支付的實現(xiàn)示例
Java數(shù)據(jù)結(jié)構(gòu)之AC自動機算法的實現(xiàn)
mybatis-plus多表聯(lián)查join的實現(xiàn)
SSH框架網(wǎng)上商城項目第25戰(zhàn)之使用java email給用戶發(fā)送郵件
如何在Spring Boot應用程序中配置了兩個不同的SOAP Web服務端點
SSH框架網(wǎng)上商城項目第27戰(zhàn)之申請域名空間和項目部署及發(fā)布
Java基于ShardingSphere實現(xiàn)分庫分表的實例詳解