通過實例學習Either 樹和模式匹配
前言
在這一期的文章中，我將繼續(xù)介紹 Either，使用它構建樹形結構，該結構允許我模擬 Scala 的模式匹配來構建遍歷方法。
在 Java 中使用泛型數據，Either 會成為接收兩種類型之一的單一數據結構，這兩種類型保存在 left 和 right 部分中。
在上一期文章的羅馬數字解析器示例中，Either 保存了 Exception（左側）或 Integer（右側），如圖 1 所示：
圖 1. Either 抽象保存了兩種類型的其中之一
在本示例中，Either以如下的方式被填充：
Either<Exception, Integer> result = RomanNumeralParser.parseNumber("XLII");
Scala 模式匹配
Scala 的眾多出色功能之一就是能夠使用 模式匹配 進行調度（參閱 參考資料）。與描述相比，演示更簡單一些，因此我們會考慮清單 1 中的函數，將數字分數轉換為字母分數：
清單 1. 使用 Scala 模式匹配根據分數調度字母分數
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 中，函數的整個正文由應用于 value 的 match 構成。對于每個選項，模式防護 允許我根據除參數類型以外的條件篩選匹配內容。這種語法的優(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)建了一個特殊的單一顏色版本。當確定將哪種顏色傳遞給函數時，我使用了 match，根據所有可用選項進行模式匹配，這些可用選項中包括最后一個 case，它將處理 null。
Java 沒有提供模式匹配，因此它無法復制 Scala 的創(chuàng)建清晰可讀的調度代碼的能力。但是，通過結合使用泛型數據結構和眾所周知的數據結構，可以實現更加接近的能力，這又將我?guī)Щ亓?Either。
Either 樹
可以建模一個具有三個抽象的樹形數據結構，如表 1 所示：
| Empty | 單元中不包含任何值 |
|---|---|
| Leaf | 單元中擁有一個特殊數據類型值 |
| Node | 指向其他 葉 或 節(jié)點 |
但是為了方便起見，我將在本例中使用來自 Functional Java 框架的一個類。從概念上講，Either 抽象擴展到了所需的方面。例如，您可以考慮聲明 Either<Empty, Either<Leaf, Node>>，這將創(chuàng)建一個三部分的數據結構，如圖 2 所示：
圖 2. Either<Empty, Either<Leaf, Node>> 的數據結構
執(zhí)行了三個樹抽象的 Either 實現之后，我定義了樹，如清單 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。從內部講，Tree 類使用 3 個插槽的 Either，如 圖 2 所示，實現這樣一種規(guī)則，即最左側的插槽總是保存 Empty，中間插槽保存 Leaf，而最右側的插槽保存 Node。方法是：請求每個類都實現 toEither() 方法，返回該類型相應的 “插槽”。從傳統(tǒng)計算機科學方面講，數據結構中的每個 “單元” 都是一個 union，旨在保存任意給定時間三種可能類型的其中一種類型。
考慮到此樹形結構和其內部結構基于 <Either, <Left, Node>> 的事實，我可以通過模擬模式匹配來訪問樹中的每個元素。
樹遍歷的模式匹配
Scala 的模式匹配鼓勵您思考離散情況。Functional Java 的 Either 實現中的 left() 和 right() 方法都實現了 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() 方法是一個遞歸深度查找函數。因為我的樹基于一個具體的數據結構（<Either, <Left, Node>>），所以我可以將每個 “插槽” 視為一個具體情況。如果單元為空，則樹枝沒有深度。如果單元為葉，則將它視為樹級別。如果單元為節(jié)點，那么我會知道應該以遞歸方式搜索左側和右側，然后添加 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;
}
與之前一樣，我在數據結構中為每個可能的 “插槽” 指定一個 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 中，我構建了樹，然后調查了是否存在元素。inTree() 方法返回 true，如果其中一個葉等于搜索值，并且 true 傳播了遞歸調用堆棧，這是因為 | ("or") 運算符，如 清單 5 所示。
清單 5 中的示例確定了元素是否出現于樹中。更復雜的版本還會檢查出現的次數，如清單 7 所示：
清單 7. 查找在樹中出現的次數
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，這使我可以計算樹中每個數字出現的次數。
清單 8 展示了復雜樹中 depth()、inTree() 和 occurrencesIn() 的測試：
清單 8. 在復雜樹中測試深度、存在狀況和出現次數
@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));
}
由于我對樹的內部結構應用了正則性，因此我可以在遍歷期間分析樹，方法是思考每種情況，如元素類型所示。該語法盡管不像完全成熟的 Scala 模式匹配一樣強大，但是與 Scala 出乎意料的接近。
結束語
在這一期的文章中，我介紹了如何在樹遍歷期間，對啟用了 Scala 風格的模式匹配應用正則性，以及如何利用泛型 Iterable 的一些固有屬性、Functional Java 的 Either 類和其他一些元素來模擬強大的 Scala 功能。
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。
相關文章
Java的集合其實就是各種基本的數據結構(棧,隊列,hash表等),基于業(yè)務需求進而演變出的Java特有的數據結構(因為不僅僅是基本數據結構),這篇文章主要給大家介紹了關于Java集合和數據結構排序的相關資料,需要的朋友可以參考下2021-08-08
本文主要介紹了SpringBoot集成支付寶沙箱支付的實現示例，文中通過示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-12-12
AC自動機算法常被認為是Trie樹+KMP算法的結合體，它是一個多模式匹配算法，在模式匹配領域被廣泛應用。本文將詳細為大家介紹AC自動機的原理與實現方法，感興趣的可以了解一下2022-12-12
這篇文章主要為大家詳細介紹了Java基于NIO實現聊天室功能，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-11-11
本文主要介紹了mybatis-plus多表聯查join的實現，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2023-01-01
在一些大型應用中，可能存在多個配置文件，這篇文章給大家介紹了Spring 整合多個配置文件的方法，非常不錯，具有一定的參考借鑒價值，感興趣的朋友一起看看吧2018-05-05
SSH框架網上商城項目第25戰(zhàn)之使用java email給用戶發(fā)送郵件
這篇文章主要為大家詳細介紹了SSH框架網上商城項目第25戰(zhàn)之使用java email給用戶發(fā)送郵件，感興趣的小伙伴們可以參考一下2016-06-06
如何在Spring Boot應用程序中配置了兩個不同的SOAP Web服務端點
這篇文章主要介紹了如何在Spring Boot應用程序中配置了兩個不同的SOAP Web服務端點,本文通過示例代碼給大家介紹的非常詳細,對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下2023-08-08
SSH框架網上商城項目第27戰(zhàn)之申請域名空間和項目部署及發(fā)布
這篇文章主要為大家詳細介紹了SSH框架網上商城項目第26戰(zhàn)之申請域名空間和項目部署及發(fā)布，感興趣的小伙伴們可以參考一下2016-06-06
Java基于ShardingSphere實現分庫分表的實例詳解
ShardingSphere?已于2020年4月16日成為?Apache?軟件基金會的頂級項目，?它們均提供標準化的數據水平擴展、分布式事務和分布式治理等功能，可適用于如?Java?同構、異構語言、云原生等各種多樣化的應用場景，對ShardingSphere分庫分表相關知識感興趣的朋友一起看看吧2022-03-03