Case Class 跟模式匹配(pattern matching)

树是常见的数据结构。如：解译器跟编译器内部常见的表示程序方式便是树；XML文件是树；还有一些容器基于树，如红黑树。

接下来我们会通过一个小型计算程序来看看 Scala 是如何表示并操作树。这个程序将足以操作仅含有整数常数、整数变量跟加法的简单算术式。1+2 跟(x+x)+(7+y) 为两个例子。

我们得先决定这种表达式的表示法。最自然表示法便是树，其中节点是操作、叶节点是值。

Java 中我们会将这个树用一个抽象父类表示，然后每种节点跟叶节点分别有各自的实际类。在函数编程里会用代数数据类型。Scala 则是提供了介于两者之间的case class。这是用其定义这样数据类型的示例：

  1. abstract class Tree
  2. case class Sum(l: Tree, r: Tree) extends Tree
  3. case class Var(n: String) extends Tree
  4. case class Const(v: Int) extends Tree

Sum、Var、Const 类定义成 case class 代表着它们跟一般类有所差别：

  • 在创建类实例时不需要用new (也就是说我们可以写Const(5)，而不是new Const(5))。
  • 对应所有构造参数，Scala 会自动定义对应的取值函数 (即，对于Const 类的实例，我们可以直接用c.v 来取得建构式中的v 参数)。
  • equals 跟hashCode 会有预设定义。该定义会根据实例的结构而不是个别实例的识别来运作。
  • toString 会有预设定义。会印出”原始型态” (即，x+1 的树会被印成Sum(Var(x),Const(1)))。
  • 这些类的实例可以借由模式匹配来拆解。

现在我们有了算术表达式的数据类型，可以开始定义各种运算。我们将从一个可以在环境内对运算式求值的函数起头。环境的用处是赋值给变量。举例来说，运算式x+1 在一个将x 赋与5 的环境 (写作{ x -> 5 } ) 下求值会得到6。

因此我们需要一个表示环境的方法。当然我们可以用一些像是哈希表的关连性数据结构，但是我们也可以直接用函数！环境就只是一个将值对应到 (变量) 名称的函数。之前提到的环境{ x -> 5 } 在 Scala 中可以简单的写作：

  1. { case "x" => 5 }

这个标记定义了一个当输入是字符串"x" 时回传整数5，其他输入则是用例外表示失败的函数。

开始之前，让我们先给环境类型一个名字。当然，我们可以直接用String => Int，但是给这类型名字可以让我们简化程序，而且在未来要改动时较为简便。在 Scala 中我们这样做：

  1. type Environment = String => Int

于是类型Environment 便可以当做输入String 回传Int 函数的类型之代名。

现在我们可以给出求值函数的定义。概念上非常简单：两个表达式和的值是两个表达式值的和；变量的值直接从环境取值；常数的值就是常数本身。表示这些在 Scala 里并不困难：

  1. def eval(t: Tree, env: Environment): Int = t match {
  2.   case Sum(l, r) => eval(l, env) + eval(r, env)
  3.   case Var(n) => env(n)
  4.   case Const(v) => v
  5. }

这个求值函数借由对树t 做模式匹配来求值。上述实作的意思应该从直观上便很明确：

  1. 首先检查树t 是否为Sum，如果是的话将左跟右侧子树绑定到新变量l跟r，然后再对箭头后方的表达式求值；这一个表达式可以使用(而且这边也用到)根据箭头左侧模式所绑定的变量，也就是l 跟r，
  2. 如果第一个检查失败，也就是说树不是Sum，接下来检查t 是否为Var，如果是的话将Var 所带的名称绑定到变量n 并求值右侧表达式，
  3. 如果第二个检查也失败，表示树不是Sum 也不是Var，那便检查是不是Const，如果是的话将Const 所带的名称绑定到变量v 并求值右侧表达式，
  4. 最后，如果全部检查都失败，会抛出异常表示匹配失败；这只会在有更多Tree 的子类时发生。

如上，模式匹配基本上就是尝试将一个值对一系列模式做匹配，并在一个模式成功匹配时抽取并命名该值的各部分，最后对一些代码求值，而这些代码通常会利用被命名到的部分。

一个经验丰富的面向对象程序员也许会疑惑为何我们不将eval 定义成Tree 类跟子类的方法。由于 Scala 允许在 case class 中跟一般类一样定义函数，事实上我们可以这样做。要用模式匹配或是函数只是品味的问题，但是这会对扩充性有重要影响。

  • 当使用函数时，增加新的节点类型是相当容易的，只要定义新的Tree 子类即可。不过另一方面，为树增加新操作很麻烦，因为它需要修改Tree 的所有子类。
  • 当使用模式匹配时情况则反过来：增加新节点需要修改所有对树做模式匹配的函数将新节点纳入考虑；增加新操作则很简单，定义新函数就好。

让我们定义新操作以更进一步的探讨模式匹配：对符号求导数。读者们可能还记得这个操作的规则：

  1. 和的导数是导数的和
  2. 如果是对变量v 取导数，变量v 的导数是1，不然就是0
  3. 常数的导数是0

这些规则几乎可以从字面上直接翻成 Scala 代码：

  1. def derive(t: Tree, v: String): Tree = t match {
  2.   case Sum(l, r) => Sum(derive(l, v), derive(r, v))
  3.   case Var(n) if (v == n) => Const(1)
  4.   case _ => Const(0)
  5. }

这个函数引入两个关于模式匹配的新观念。首先，变量的case 运算式有一个看守，也就是if 关键字之后的表达式。除非表达式求值为真，不然这个看守会让匹配直接失败。在这边是用来确定我们只在取导数变量跟被取导数变量名称相同时才回传常数1。第二个新特征是可以匹配任何值的万用字符_。

我们还没有探讨完模式匹配的全部功能，不过为了让这份文件保持简短，先就此打住。我们还是希望能看到这两个函数在真正的示例如何作用。因此让我们写一个简单的main 函数，对表达式(x+x)+(7+y) 做一些操作：先在环境{ x -> 5, y -> 7 } 下计算结果，然后在对x 接着对y 取导数。

  1. def main(args: Array[String]) {
  2.   val exp: Tree = Sum(Sum(Var("x"),Var("x")),Sum(Const(7),Var("y")))
  3.   val env: Environment = { case "x" => 5 case "y" => 7 }
  4.   println("Expression: " + exp)
  5.   println("Evaluation with x=5, y=7: " + eval(exp, env))
  6.   println("Derivative relative to x:\n " + derive(exp, "x"))
  7.   println("Derivative relative to y:\n " + derive(exp, "y"))
  8. }

执行这程序，得到预期的输出：

  1. Expression: Sum(Sum(Var(x),Var(x)),Sum(Const(7),Var(y)))
  2. Evaluation with x=5, y=7: 24
  3. Derivative relative to x:
  4.  Sum(Sum(Const(1),Const(1)),Sum(Const(0),Const(0)))
  5. Derivative relative to y:
  6.  Sum(Sum(Const(0),Const(0)),Sum(Const(0),Const(1)))

研究这输出我们可以发现，取导数的结果应该在输出前更进一步化简。用模式匹配实现一个基本化简函数是一个很有趣 (但是意外的棘手) 的问题，在这边留给读者当练习。