通过实例学习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 所示:

Empty 单元中不包含任何值
Leaf 单元中拥有一个特殊数据类型值
Node 指向其他 叶 或 节点

但是为了方便起见,我将在本例中使用来自 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 功能。

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

(0)

相关推荐

  • 如何利用 Either 和 Option 进行函数式错误处理

    前言 我将讨论 Scala 风格的模式匹配,但首先我需要通过 Either 概念建立一些背景知识.Either 的其中一个用法是函数式风格的错误处理,我会在本期文章中对其进行介绍. 在 Java 中,错误的处理在传统上由异常以及创建和传播异常的语言支持进行.但是,如果不存在结构化异常处理又如何呢?许多函数式语言不支持异常范式,所以它们必须找到表达错误条件的替代方式.在本文中,我将演示 Java 中类型安全的错误处理机制,该机制绕过正常的异常传播机制(并通过 Functional Java 框架的

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

    前言 在这一期的文章中,我将继续介绍 Either,使用它构建树形结构,该结构允许我模拟 Scala 的模式匹配来构建遍历方法. 在 Java 中使用泛型数据,Either 会成为接收两种类型之一的单一数据结构,这两种类型保存在 left 和 right 部分中. 在上一期文章的罗马数字解析器示例中,Either 保存了 Exception(左侧)或 Integer(右侧),如图 1 所示: 图 1. Either 抽象保存了两种类型的其中之一 在本示例中,Either以如下的方式被填充: Ei

  • Bootstrap 树控件使用经验分享(图文解说)

    jquery 树形控件 jquery 树形控件是一款基于jquery+bootstrap.完全通过js和样式手写出来的非常轻量级的控件,它功能简单.用户体验不错.对于一些简单的层级关系展示比较实用. 前言:很多时候我们在项目中需要用到树,有些树仅仅是展示层级关系,有些树是为了展示和编辑层级关系,还有些树是为了选中项然后其他地方调用选中项.不管怎么样,树控件都是很多项目里面不可或缺的组件之一.今天,博主打算结合自己的使用经历和网上找到的一些不错的树控件在这里做一个分享,希望能帮大家找到最合适的控件

  • 学习YUI.Ext 第六天--关于树TreePanel(Part 2异步获取节点)

    下面将介绍如何异步取一棵树的所有节点,具体做法与官方同步取节点有很大不同,尤其在json的id属性上,下面是我一些摸索,可能不是最佳方案,有待大家一起研究. 异步取节点的思路是这样的: 1.先定义一个初始化节点(也可以不定义,看个人需求) 2.yui-ext根据该节点id请求服务器,获得子节点各属性 3.循环 特点:可以在上一级目录中,在服务器端预先将该节点是否有子节点读好(json中的isLeaf属性),虽然但数据库将多承担一些压力,但用个count(*)不会造成太大负担(除非查询条件异常复杂

  • Easy UI动态树点击文字实现展开关闭功能

    只需要在JSP处,点击树的函数中,添加一段代码即可: 整体如下: <span style="white-space:pre"> </span>$("#tt").tree({ onClick: function(node){ if(node.url != null){ parent.frames["content"].location.href="${ctx}" rel="external no

  • 利用Dojo和JSON建立无限级AJAX动态加载的功能模块树

    看了"使用hibernate实现树形结构无限级分类"这篇文章后,我也想将自己在所有开发的项目中使用的功能模块树的实现方法以及完整DEMO(含源码)贴出来和大家分享.其实在我的博客里是老早贴出来的,由于时间关系没好好整理.        功能模块树是几乎在每个项目里都要用到的东西,利用Dojo的好处就是可以实现树的子节点的动态加载,这在树节点很多的情况下是很有用的.         下载附件二dojotree.rar,解压后将dist\dojotree.war部署到应用服务器即可浏览DE

  • JavaScript实现树的遍历算法示例【广度优先与深度优先】

    本文实例讲述了JavaScript实现树的遍历算法.分享给大家供大家参考,具体如下: <script type="text/javascript"> var t = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19]; //下面这段深度优先搜索方法出自Aimingoo的[JavaScript语言精髓与编程实践] var deepView = function(aTree,iNode) { (iNode in aTree)

  • Perl中的模式匹配学习笔记

    一.简介 模式指在字符串中寻找的特定序列的字符,由反斜线包含:/def/即模式def.其用法如结合函数split将字符串用某模式分成多个单词:@array = split(/ /, $line); 二.匹配操作符 =~.!~ =~检验匹配是否成功:$result = $var =~ /abc/;若在该字符串中找到了该模式,则返回非零值,即true,不匹配则返回0,即false.!~则相反.这两个操作符适于条件控制中,如: 复制代码 代码如下: if ($question =~ /please/)

  • asp.net使用DataGridTree实现下拉树的方法

    本文实例讲述了asp.net使用DataGridTree实现下拉树的方法.分享给大家供大家参考.具体实现方法如下: 下拉树实现原理:输出json到客户端,客户端实现动态加载,中间不会和服务端交互.数据量支持上经测试几千还是很快的.本下拉树控件是用c#+js树实现. 2.c# 计算器 计算字符串数学表达式源码 计算数学表达式原理 采用c#实现 很实用 //a.建立两个栈:第一个位操作数栈,第二个操作符符栈!(将栈定义为string类型) //b.对数字来说是无条件压入数字栈中. //c.而对符号来

  • Python基于回溯法子集树模板实现8皇后问题

    本文实例讲述了Python基于回溯法子集树模板实现8皇后问题.分享给大家供大家参考,具体如下: 问题 8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行.同一列或同一斜线上,问有多少种摆法. 分析 为了简化问题,考虑到8个皇后不同行,则每一行放置一个皇后,每一行的皇后可以放置于第0.1.2.....7列,我们认为每一行的皇后有8种状态.那么,我们只要套用子集树模板,从第0行开始,自上而下,对每一行的皇后,遍历它的8个状态即可. 代码: ''' 8皇后问题 '''

  • C语言二叉排序(搜索)树实例

    本文实例为大家分享了C语言二叉排序(搜索)树实例代码,供大家参考,具体内容如下 /**1.实现了递归 非递归插入(创建)二叉排序(搜索)树: 分别对应Insert_BinSNode(TBinSNode* T,int k),NonRecursion_Insert_BinSNode(TBinSNode* T,int k); 2.实现了递归 非递归查找 二叉排序(搜索)树 : 分别对应Find_BinSNode(TBinSNode *T,int s),NonRecursion_Find_BinSNod

随机推荐