通過實例學習Either 樹和模式匹配
前言
在這一期的文章中，我將繼續(xù)介紹 Either，使用它構建樹形結構，該結構允許我模擬 Scala 的模式匹配來構建遍歷方法。
在 Java 中使用泛型數(shù)據(jù)，Either 會成為接收兩種類型之一的單一數(shù)據(jù)結構，這兩種類型保存在 left 和 right 部分中。
在上一期文章的羅馬數(shù)字解析器示例中，Either 保存了 Exception（左側）或 Integer（右側），如圖 1 所示：
圖 1. Either 抽象保存了兩種類型的其中之一
在本示例中，Either以如下的方式被填充：
Either<Exception, Integer> result = RomanNumeralParser.parseNumber("XLII");
Scala 模式匹配
Scala 的眾多出色功能之一就是能夠使用 模式匹配 進行調度（參閱 參考資料）。與描述相比，演示更簡單一些，因此我們會考慮清單 1 中的函數(shù)，將數(shù)字分數(shù)轉換為字母分數(shù)：
清單 1. 使用 Scala 模式匹配根據(jù)分數(shù)調度字母分數(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 構成。對于每個選項，模式防護 允許我根據(jù)除參數(shù)類型以外的條件篩選匹配內容。這種語法的優(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)建清晰可讀的調度代碼的能力。但是，通過結合使用泛型數(shù)據(jù)結構和眾所周知的數(shù)據(jù)結構，可以實現(xiàn)更加接近的能力，這又將我?guī)Щ亓?Either。
Either 樹
可以建模一個具有三個抽象的樹形數(shù)據(jù)結構，如表 1 所示：
| Empty | 單元中不包含任何值 |
|---|---|
| Leaf | 單元中擁有一個特殊數(shù)據(jù)類型值 |
| Node | 指向其他 葉 或 節(jié)點 |
但是為了方便起見，我將在本例中使用來自 Functional Java 框架的一個類。從概念上講，Either 抽象擴展到了所需的方面。例如，您可以考慮聲明 Either<Empty, Either<Leaf, Node>>，這將創(chuàng)建一個三部分的數(shù)據(jù)結構，如圖 2 所示：
圖 2. Either<Empty, Either<Leaf, Node>> 的數(shù)據(jù)結構
執(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。從內部講，Tree 類使用 3 個插槽的 Either，如 圖 2 所示，實現(xiàn)這樣一種規(guī)則，即最左側的插槽總是保存 Empty，中間插槽保存 Leaf，而最右側的插槽保存 Node。方法是：請求每個類都實現(xiàn) toEither() 方法，返回該類型相應的 “插槽”。從傳統(tǒng)計算機科學方面講，數(shù)據(jù)結構中的每個 “單元” 都是一個 union，旨在保存任意給定時間三種可能類型的其中一種類型。
考慮到此樹形結構和其內部結構基于 <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ù)結構（<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;
}
與之前一樣，我在數(shù)據(jù)結構中為每個可能的 “插槽” 指定一個 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 中的示例確定了元素是否出現(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));
}
由于我對樹的內部結構應用了正則性，因此我可以在遍歷期間分析樹，方法是思考每種情況，如元素類型所示。該語法盡管不像完全成熟的 Scala 模式匹配一樣強大，但是與 Scala 出乎意料的接近。
結束語
在這一期的文章中，我介紹了如何在樹遍歷期間，對啟用了 Scala 風格的模式匹配應用正則性，以及如何利用泛型 Iterable 的一些固有屬性、Functional Java 的 Either 類和其他一些元素來模擬強大的 Scala 功能。
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。
相關文章
java利用java.net.URLConnection發(fā)送HTTP請求的方法詳解
如何通過Java（模擬瀏覽器）發(fā)送HTTP請求是我們在日常經(jīng)常會遇到的問題，下面這篇文章主要給大家介紹了關于java利用java.net.URLConnection發(fā)送HTTP請求的相關資料，文中介紹的非常詳細，需要的朋友可以參考借鑒，下面來一起看看吧。2017-05-05
Emoji 實際上是 UTF-8 (Unicode) 字符集上的特殊字符,這篇文章主要介紹了如何使用Java實現(xiàn)查找并移除字符串中的Emoji,感興趣的可以了解下2024-03-03
SpringBoot整合Quartz實現(xiàn)動態(tài)配置的代碼示例
這篇文章將介紹如何把Quartz定時任務做成接口，實現(xiàn)以下功能的動態(tài)配置添加任務，修改任務，暫停任務，恢復任務，刪除任務，任務列表，任務詳情，文章通過代碼示例介紹的非常詳細,需要的朋友可以參考下2023-07-07
SpringBoot集成I18n國際化文件在jar包外生效問題
這篇文章主要介紹了SpringBoot集成I18n國際化文件在jar包外生效問題,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2024-04-04
這篇文章主要介紹了maven打包時候修改包名稱帶上git版本號和打包時間方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2023-04-04
EhCache是一個比較成熟的Java緩存框架，Springboot對ehcache的使用非常支持，所以在Springboot中只需做些配置就可使用，且使用方式也簡易，今天給大家分享springboot ehcache 配置使用教程，一起看看吧2021-06-06
這篇文章主要介紹了Java中類的加載順序執(zhí)行結果的相關資料,需要的朋友可以參考下2017-10-10
這篇文章主要介紹了SpringMVC ModelAndView的用法使用詳解，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2019-12-12
SpringBoot分布式文件存儲數(shù)據(jù)庫mongod
MongoDB是一個基于分布式文件存儲的NoSQL數(shù)據(jù)庫，由C++語言編寫，旨在為Web應用提供可擴展的高性能數(shù)據(jù)存儲解決方案。MongoDB是一個介于關系數(shù)據(jù)庫和非關系數(shù)據(jù)庫之間的產(chǎn)品，是非關系數(shù)據(jù)庫中功能最豐富最像關系數(shù)據(jù)庫的2023-02-02
這篇文章主要介紹了Java實現(xiàn)歐拉函數(shù)的計算,從歐拉函數(shù)引伸出來在環(huán)論方面的事實和拉格朗日定理構成了歐拉定理的證明，本文通過實例代碼給大家介紹的很詳細，需要的朋友可以參考下2021-05-05