数码控科技猎奇Iphone动漫星座游戏电竞lolcosplay王者荣耀攻略allcnewsBLOGNEWSBLOGASKBLOGBLOGZSK全部技术问答问答技术问答it问答代码软件新闻开发博客电脑/网络手机/数码笔记本电脑互联网操作系统软件硬件编程开发360产品资源分享电脑知识文档中心IT全部全部分类全部分类技术牛文全部分类教程最新网页制作cms教程平面设计媒体动画操作系统网站运营网络安全服务器教程数据库工具网络安全软件教学vbscript正则表达式javascript批处理更多»编程更新教程更新游戏更新allitnewsJava新闻网络医疗信息化安全创业站长电商科技访谈域名会议专栏创业动态融资创投创业学院 / 产品经理创业公司人物访谈营销开发数据库服务器系统虚拟化云计算嵌入式移动开发作业作业1常见软件all电脑网络手机数码生活游戏体育运动明星影音休闲爱好文化艺术社会民生教育科学医疗健康金融管理情感社交地区其他电脑互联网软件硬件编程开发360相关产品手机平板其他电子产品摄影器材360硬件通讯智能设备购物时尚生活常识美容塑身服装服饰出行旅游交通汽车购房置业家居装修美食烹饪单机电脑游戏网页游戏电视游戏桌游棋牌游戏手机游戏小游戏掌机游戏客户端游戏集体游戏其他游戏体育赛事篮球足球其他运动球类运动赛车健身运动运动用品影视娱乐人物音乐动漫摄影摄像收藏宠物幽默搞笑起名花鸟鱼虫茶艺彩票星座占卜书画美术舞蹈小说图书器乐声乐小品相声戏剧戏曲手工艺品历史话题时事政治就业职场军事国防节日风俗法律法规宗教礼仪礼节自然灾害360维权社会人物升学入学人文社科外语资格考试公务员留学出国家庭教育学习方法语文物理生物工程学农业数学化学健康知识心理健康孕育早教内科外科妇产科儿科皮肤科五官科男科整形中医药品传染科其他疾病医院两性肿瘤科创业投资企业管理财务税务银行股票金融理财基金债券保险贸易商务文书国民经济爱情婚姻家庭烦恼北京上海重庆天津黑龙江吉林辽宁河北内蒙古山西陕西宁夏甘肃青海新疆西藏四川贵州云南河南湖北湖南山东江苏浙江安徽江西福建广东广西海南香港澳门台湾海外地区

通过实例学习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 功能。

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

您可能感兴趣的文章:


  • 本文相关:
  • 如何利用 either 和 option 进行函数式错误处理
  • javaweb实现文件上传与下载实例详解
  • java多线程之callable接口的实现
  • springboot 调度任务及常用任务表达式
  • java版ai五子棋游戏
  • java利用swagger2自动生成对外接口的文档
  • spring boot 入门之消息中间件的使用
  • springboot集成测试里的redis
  • java中实体类和json对象之间相互转化
  • java 函数的重载和重写实例代码
  • java8中lamba表达式的使用
  • 免责声明 - 关于我们 - 联系我们 - 广告联系 - 友情链接 - 帮助中心 - 频道导航
    Copyright © 2017 www.zgxue.com All Rights Reserved