函数式思维: Either 树和模式匹配

使用 Either 和泛型在 Java 中创建 Scala 风格的模式匹配

Scala 基于模式匹配执行调度的能力是 Java™ 开发人员都很羡慕的一个功能。这一期的文章展示了如何结合使用标准数据结构和泛型数据结构在纯 Java 语言中提供与模式匹配类似的语法。

Neal Ford, 软件架构师, ThoughtWorks Inc.

Neal FordNeal Ford 是一家全球性 IT 咨询公司 ThoughtWorks 的软件架构师和 Meme Wrangler。他的工作还包括设计和开发应用程序、教材、杂志文章、课件和视频/DVD 演示,而且他是各种技术书籍的作者或编辑,包括最近的新书 The Productive Programmer。他主要的工作重心是设计和构建大型企业应用程序。他还是全球开发人员会议上的国际知名演说家。请访问他的 Web 站点



2012 年 8 月 27 日

关于本系列

本系列文章旨在将您的思维方式向函数式思维方式的方向调整,让您以全新的角度来思考常见问题,并提高您的日常编码工作。本系列介绍了函数式编程概念,函数式编程在 Java 语言中运行的框架、在 JVM 上运行的函数式编程语言,以及语言设计未来的一些方向。本系列主要面向了解 Java 以及其抽象层的工作原理、但缺乏函数式语言使用经验的开发人员。

上一期文章 中,我介绍了函数式编程世界的一种通用抽象:Either。在这一期的文章中,我将继续介绍 Either,使用它构建树形结构,该结构允许我模拟 Scala 的模式匹配来构建遍历方法。

在 Java 中使用泛型数据,Either 会成为接收两种类型之一的单一数据结构,这两种类型保存在 leftright 部分中。

在上一期文章的罗马数字解析器示例中,Either 保存了 Exception(左侧)或 Integer(右侧),如图 1 所示:

图 1. Either 抽象保存了两种类型的其中之一
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 中,函数的整个正文由应用于 valuematch 构成。对于每个选项,模式防护 允许我根据除参数类型以外的条件筛选匹配内容。这种语法的优势是一个干净的选项分区,而不是一系列复杂的 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 所示:

表 1. 构建一个具有三个抽象的树
Empty单元中不包含任何值
Leaf单元中拥有一个特殊数据类型值
Node指向其他 节点

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

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

执行了三个树抽象的 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 具体类:EmptyLeafNode。从内部讲,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 功能。

在下一期的文章中,我将介绍下一代 Java 语言中出现的各种方法调度机制,并 Java 中可用的有限选项进行对比。

参考资料

学习

获得产品和技术

讨论

  • 加入 developerWorks 中文社区。查看开发人员推动的博客、论坛、组和维基,并与其他 developerWorks 用户交流。

条评论

developerWorks: 登录

标有星(*)号的字段是必填字段。


需要一个 IBM ID?
忘记 IBM ID?


忘记密码?
更改您的密码

单击提交则表示您同意developerWorks 的条款和条件。 查看条款和条件

 


在您首次登录 developerWorks 时,会为您创建一份个人概要。您的个人概要中的信息(您的姓名、国家/地区,以及公司名称)是公开显示的,而且会随着您发布的任何内容一起显示,除非您选择隐藏您的公司名称。您可以随时更新您的 IBM 帐户。

所有提交的信息确保安全。

选择您的昵称



当您初次登录到 developerWorks 时,将会为您创建一份概要信息,您需要指定一个昵称。您的昵称将和您在 developerWorks 发布的内容显示在一起。

昵称长度在 3 至 31 个字符之间。 您的昵称在 developerWorks 社区中必须是唯一的,并且出于隐私保护的原因,不能是您的电子邮件地址。

标有星(*)号的字段是必填字段。

(昵称长度在 3 至 31 个字符之间)

单击提交则表示您同意developerWorks 的条款和条件。 查看条款和条件.

 


所有提交的信息确保安全。


static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=10
Zone=Java technology
ArticleID=831943
ArticleTitle=函数式思维: Either 树和模式匹配
publish-date=08272012