串的模式匹配是什么？

串的模式匹配即子串定位，是一种重要的串的运算。设S是给定的主串，T是给定的子串，在主串S中查找等于子串T的串的过程称为模式匹配，T称为模式串。如果在S中找到T子串，则称匹配成功，函数返回T在S中首次出现的存储位置（或序号），否则匹配失败，返回0。为了运算方便，假设串采用顺序存储结构，串的长度存放在0号单元，串值从1号单元开始存放，这样字符序号与存储位置一致。

在这篇martin和另外两位模式匹配领域专家的论文里说了模式匹配的几种实现方式，以及scala是选择哪种方式来实现的。

我引用了里面的一些描述。

在面向对象的程序中数据被组织为一级一级的类(class)，面向对象语言在模式匹配方面的问题在于如何从外部探测这个层级。

有6种实现模式匹配的方法：

面向对象的分解 (decomposition)

访问器模式 (visitor)

类型测试/类型造型 (type-test/type-cast)

typecase

样本类 (case class)

抽取器 (extractor)

论文里从3个维度9个标准来对比了各种实现方式:

简明程度(框架支持、浅匹配、深匹配)，维护性(表征独立、扩展性)，性能(基础性能、广度和深度延展性)

比较的细节在这篇论文里有提，不一一展开。最终scala选择了采用 样本类(case class) 和 抽取器(extractor) 来实现模式匹配。我们大致了解一下case class和extractor 是怎么回事

1)样本类(case class)

本质上case class是个语法糖，对你的类构造参数增加了getter访问，还有toString, hashCode, equals 等方法；

最重要的是帮你实现了一个伴生对象，这个伴生对象里定义了apply 方法和 unapply 方法。

apply方法是用于在构造对象时，减少new关键字；而unapply方法则是为模式匹配所服务。

这两个方法可以看做两个相反的行为，apply是构造(工厂模式)，unapply是分解(解构模式)。

case class在暴露了它的构造方式，所以要注意应用场景：当我们想要把某个类型暴露给客户，但又想要隐藏其数据表征时不适宜。

2) 抽取器(extrator)

抽取器是指定义了unapply方法的object。在进行模式匹配的时候会调用该方法。

unapply方法接受一个数据类型，返回另一数据类型，表示可以把入参的数据解构为返回的数据。

比如

class A

class B(val a:A)

object TT {

   def unapply(b:B) = Some(new A)

}

这样定义了抽取器TT后，看看模式匹配：

val b = new B(new A)

b match{ case TT(a) =>println(a) }

直观上以为 要拿b和TT类型匹配，实际被翻译为

TT.unapply(b)  match{ case Some(…) =>… }

它与上面的case class相比，相当于自己手动实现unapply，这也带来了灵活性。

后续会专门介绍一下extrator，这里先看一下extractor怎么实现case class无法实现的“表征独立”(representation independence)

比如我们想要暴露的类型为A

//定义为抽象类型

trait A

//然后再实现一个具体的子类，有2个构造参数

class B (val p1:String, val p2:String) extends A

//定义一个抽取器

object MM{

   //抽取器中apply方法是可选的，这里是为了方便构造A的实例

   def apply(p1:String, p2:String) : A = new B(p1,p2)

   //把A分解为(String,String)

   def unapply(a:A) : Option[(String, String)] = {

       if (a.isInstanceOf[B]) {

        val b = a.asInstanceOf[B]

        return Some(b.p1, b.p2)

       }

       None

   }

}

这样客户只需要通过 MM(x,y) 来构造和模式匹配了。客户只需要和MM这个工厂/解构角色打交道，A的实现怎么改变都不受影响。

注：

有很多的资料里在介绍case class时经常把它和函数式语言里的代数数据类对比(ADT)。严格的说Scala中的case class并不是ADT，但比较靠近，可以模拟ADT。

这篇文章中提到case class介于类继承和代数数据类型之间

“Scala则提供了一种介于两者之间（类继承和代数数据类型），被称为条件类（case classes）的概念”

《Programming in Scala》中文版，在术语表中也有提到ADT：

通过提供若干个含有独立构造器的备选项(alternative)来定义的类型。通常可以辅助于通过模式匹配解构类型的方式。这个概念可以在规约语言和函数式语言中发现。代数数据类型在Scala中可以用样本类(case class)模拟。

先抛个问题，下面的语句是否都合理(编译通过)，哪些会引起模式匹配？

scala>val a = 100

scala>val A = 100

scala>val a@b = 100

scala>val (a,b) = (100,200)

scala>val (a,B) = (100,200)//第二个变量大写

scala>val Array(a,b) = Array(100,200)

scala>val Array(a,B) = Array(100,200)

scala>object Test { val 2 = 2 }

scala>object Test { val 2 = 3 }

我们先看看其他语言(对scala有影响的)有关赋值语句的定义：

1) 在 ML 语言里，对赋值语句的定义：

val P = E

表示定义了模式P中的变量，并赋予它们表达式E中相应的值。

2) 在Erlang中等号 = 表示一个模式匹配 *** 作

在这两种语言中，赋值语句都明确的定义为模式匹配，那么scala中，所有的赋值语句是否都是模式匹配呢？

尤其scala可以说在函数式风格上与ML(及其家族)语言有某种血缘，在这一点上是否也与ML完全一致呢？

先分析一下上面的每条赋值语句：val a = 100 和 val A = 100是直观且没有歧义的。

val a@b = 100 是什么意思？回忆一下第一篇里讲过的“变量绑定模式”，当时的例子有点复杂，重新理解一下：

//给"hello"字符串对象用v1这个变量名

scala>"hello" match { case v1 =>println(v1) }

//变量绑定模式，把变量v2 绑定在v1这个模式上

scala>"hello" match { case v2@v1 =>println(v2) }

上面的例子中，第一行中v1是个变量模式。 第二行中v2是一个新的变量，只有在v1这个模式匹配成功的情况下，才会把自己绑定到v1上，而v1因为是一个变量模式，它总能匹配成功，所以这里v2也会绑定到”hello”对象上。变量绑定模式通常不会这么使用，更多用在绑定到一个复合结构的模式上，如：

scala>List(1,List(2,3)) match { case List(_, x@List(2,_*)) =>println(x.size) }

2

把变量x绑定到了嵌套的 List(2,3) 这个对象上

但赋值语句val a@b = 100 跟上面的有关系么？我们通过ToolBox看看它”脱糖”后的语法树：

scala>tb.parse("val a@b=100")

res13: tb.u.Tree =

{

<synthetic>private[this] val x$3 = 100: @scala.unchecked match {

case (a @ (b @ _)) =>scala.Tuple2(a, b) //这一句

}

val a = x$3._1

val b = x$3._2

}

有注释的那一句里面把a,b两个局部变量绑定到通配符”_”上，而这个通配符模式case _ =>可以匹配任何对象，所以相当于把a,b两个变量绑定到了100这个对象上，并产生了一个二元组记录这两个局部变量值。最终把二元组里的值分别赋给了我们定义的a，b两个变量。

接下来的val (a,b) = (100,200) 这个赋值也容易理解，把二元组里的值分别赋给a，b两个变量么，也是经过模式匹配的么？继续用ToolBox分析：

scala>tb.parse("val (a,b)=(100,200)")

res14: tb.u.Tree =

{

<synthetic>private[this] val x$4 = scala.Tuple2(100, 200): @scala.unchecked match {

case scala.Tuple2((a @ _), (b @ _)) =>scala.Tuple2(a, b)

}

val a = x$4._1

val b = x$4._2

}

看到了，是一个构造器模式与变量绑定模式的混合模式匹配。

再下一个val (a,B) = (100,200) 这个与上一个有区别么？回顾一下第一篇里讲到的“常量模式”：当变量大写时将被对待为常量模式，也就是说 大写B 和上面的 小写b 是两种不同的模式！！

scala>tb.parse("val (a,B)=(100,200)")

res15: tb.u.Tree =

val a = scala.Tuple2(100, 200): @scala.unchecked match {

case scala.Tuple2((a @ _), B) =>a

}

大写B在这里当作常量来解析，但又找不到B这个变量(除非之前有定义过)，就报错了：

scala>val (a,B) = (100,200)

<console>:8: error: not found: value B

val (a,B) = (100,200)

^

后边两个Array的赋值语句与这两个类似，小括号写法只是元组(Tuple)的语法糖而已。

最后，真正有趣，且会让新手崩溃的情况 object Test { val 2 = 2 } 为什么这个编译和初始化都没问题？

scala>object Test { val 2 = 2 }

defined module Test

scala>Test

res16: Test.type = Test$@3042dc22

简直逆天，难道这个背后也与模式匹配有关系么？

scala>tb.parse(" object Test { val 2 = 2 }")

res0: tb.u.Tree =

object Test extends scala.AnyRef {

def <init>() = {

super.<init>()

()

}

<synthetic>private[this] val x$1 = 2: @scala.unchecked match {

case 2 =>()

}

}

确实又是一个常量模式匹配，2匹配2，成功。

同理，下一个 object Test { val 2 = 3 } 也是个常量模式匹配，但为何明显不匹配，却可以编译时成功，而运行时时才报错呢？

scala>object Test { val 2 = 3 }

defined module Test

scala>Test

scala.MatchError: 3 (of class java.lang.Integer)

at Test$.<init>(<console>:8)

这是因为object 是惰性初始化的原因(lazy)，如下:

// 对下面的单例

object Test { val a = 2 }

$ scalac -Xprint:jvm A.scala

package <empty>{

object Test extends Object {

private[this] val a: Int = _

<stable><accessor>def a(): Int = Test.this.a

def <init>(): Test.type = {

Test.super.<init>()

Test.this.a = 2 //在初始化时才对成员赋值

()

}

}

}

在对多个变量赋值，或变量中有@符合，导致模式匹配还好理解，但”2=2″也引起模式匹配就会让我产生疑问：

是否所有的赋值语句都是模式匹配?

为了验证，通过编译选项查看val a=2 这样对单个变量的赋值却没有看到模式匹配。

另外，如果单个变量也是模式匹配，为何大写字母val A=2没问题？假设对单个变量赋值也是模式匹配，那岂不无法定义大写的变量了；肯定是有区别的，但又怎么区分的？

我最初遇到这个困惑，在邮件列表里问了这个问题，得到了一些回复，并且有人给了一个老帖子链接说早就讨论过val 1=2这个话题了：

在那个帖子里，martin也回复了为何 val 1=2是模式匹配，并且为何不把这种情况作为错误给修复掉：

A value definition is of the form

val <pattern>= <expression>// 这个同ML和Erlang语言

1 is a <pattern>

There is one edge case:

If the pattern is a single variable (upper or lower case or backquoted), then it is always treated as a variable, not a constant. Otherwise, there would be no way to define such a value.

只有一种边缘情况：如果模式是一个单独的变量(大写、小写、或用反引号引起来的)，那么它总被当作变量，而非常量。否则就没法定义这样的一个值。

所以1=2, "a"="b" 这样的赋值语句虽然是一个变量，但变量名称不符合上面的约束，产生了模式匹配。至于为何不修复这个问题(直接在编译时报错)，也可以从这个帖子的线索中找到原因。

---