通过实例学习Either 树和模式匹配

前言

在这一期的文章中，我将继续介绍 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 构成。对于每个选项，模式防护 允许我根据除参数类型以外的条件筛选匹配内容。这种语法的优势是一个干净的选项分区，而不是一系列复杂的 if 语句。

模式匹配与 Scala 的 case 类一同工作，该类是具有特殊属性的类 （包括执行模式匹配的能力），以消除决策序列。考虑匹配颜色组合，如清单 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 中，我创建了一个基本 Color 类，然后与 case 类一样，创建了一个特殊的单一颜色版本。当确定将哪种颜色传递给函数时，我使用了 match，根据所有可用选项进行模式匹配，这些可用选项中包括最后一个 case，它将处理 null。

Java 没有提供模式匹配，因此它无法复制 Scala 的创建清晰可读的调度代码的能力。但是，通过结合使用泛型数据结构和众所周知的数据结构，可以实现更加接近的能力，这又将我带回了 Either。

Either 树

可以建模一个具有三个抽象的树形数据结构，如表 1 所示：

但是为了方便起见，我将在本例中使用来自 Functional Java 框架的一个类。从概念上讲，Either 抽象扩展到了所需的方面。例如，您可以考虑声明 Either<Empty, Either<Leaf, Node>>，这将创建一个三部分的数据结构，如图 2 所示：

图 2. Either<Empty, Either<Leaf, Node>> 的数据结构

执行了三个树抽象的 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 所示，实现这样一种规则，即最左侧的插槽总是保存 Empty，中间插槽保存 Leaf，而最右侧的插槽保存 Node。方法是：请求每个类都实现 toEither() 方法，返回该类型相应的 “插槽”。从传统计算机科学方面讲，数据结构中的每个 “单元” 都是一个 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>>），所以我可以将每个 “插槽” 视为一个具体情况。如果单元为空，则树枝没有深度。如果单元为叶，则将它视为树级别。如果单元为节点，那么我会知道应该以递归方式搜索左侧和右侧，然后添加 1 进行另一次递归。

我还可以使用相同的模式匹配语法来执行树的递归搜索，如清单 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。否则，在遇到节点时，我会遍历树，使用 |（非短路的 or 运算符）来组合返回的布尔值。

要查看实际的树创建和搜索，请考虑清单 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 功能。

来源：https://www.ibm.com/developerworks/cn/java/j-ft14/index.html?ca=drs-