模式匹配

  此條目介紹的是函数式编程中的模式匹配。关于其他用法，请见「字串搜尋演算法」和「模式识别」。

  关于在定义要匹配的抽象模式时使用可变的匹配准则，请见「正则表达式」。

在计算机科学中，模式匹配是检查给定记号序列中，是否存在某种模式的组成部分的行为。与模式识别相反，匹配通常必须是精确的。模式通常具有序列或树状结构的形式。模式匹配的用途包括：输出一个模式在一个记号序列中的位置（如果有的话），输出匹配模式的一些组成部份，以及用一些其他的记号序列替换匹配模式（即搜索和替换）。

概述

在一些编程语言中，模式被用作一种通用工具，基于数据的结构来处理数据，包括C#^[1]、 F#^[2]、Haskell^[3]、ML、Python^[4]、Ruby^[5]、Rust^[6]、Scala^[7]、Swift^[8]和Mathematica的符号式Wolfram语言，它们拥有表达树状结构的特殊语法，和基于它的条件执行和值检索的语言构造（英语：Language construct）。

经常可以给出逐个尝试的交替（英语：Alternation (formal language theory)）式模式，它产生强力的条件编程构造^[9]。模式匹配有时包括对守卫子句的支持^[10]。

字符序列也就是字符串，经常使用正则表达式来描述，并使用像回溯这样的技术来进行匹配。解析算法经常依赖模式匹配来将字符串变换成语法树^[11][12]。

历史

具有模式匹配构造的早期编程语言包括：COMIT（1957年）、SNOBOL（1962年）、具有树状模式的Refal（英语：Refal）（1968年）、Prolog（1972年）、SASL（1976年）、NPL（1977年）和KRC（1981年）。

很多文本编辑器支持各种的模式匹配：支持正则表达式查找的QED编辑器（英语：QED (text editor)），和在查找中支持OR运算的某些版本的TECO（英语：TECO (text editor)）。计算机代数系统一般支持在代数表达式上的模式匹配^[13]。

简单模式

在模式匹配中，最简单的模式是一个明确的值或一个变量。例如，考虑采用Haskell语法的一个简单函数，这里函数参数不放在圆括号内但用空白分隔，=不是赋值而是定义：

f 0 = 1 

这里的0是一个单一值模式。只要f被给予0作为参数，这个模式就匹配，并且函数返回1。对于任何其他参数，匹配失败，因而这个函数也失败。因为在函数定义中，语法上支持交替式模式，可以继续将定义扩展为接受更一般性的参数：

f n = n * f (n-1) 

这里的第一个n是单一变量模式，它绝对的匹配任何参数，并将它绑定到名字n，而用在定义的余下部份之中。在Haskell中（至少不似Hope），模式被依次尝试，所以第一个定义仍适用于输入是0的非常特殊情况，而对于任何其他参数，函数返回n * f (n-1)，具有n是为参数。

通配符模式（通常写为_）也是简单的：就像一个变量名字，它匹配任何值，但是不把这个值绑定到任何名字。在简单字符串匹配情况下的匹配通配符（英语：Matching wildcards）算法，已经发展出很多递归和非递归的变体^[14]。

在Haskell中，下面的代码定义了一个代数数据类型Color，它有一个单一的数据构造子ColorConstructor，包装一个整数和一个字符串：

data Color = ColorConstructor Integer String 

例如，要得到Color类型的整数部份的一个函数可以写为：

integerPart (ColorConstructor theInteger _) = theInteger 

要得到字符串部份：

stringPart (ColorConstructor _ theString) = theString 

这些函数可以通过Haskell的数据记录语法自动创建。

模式匹配还可应用来过滤特定结构的数据。例如，在Haskell中可以使用列表推导式进行这种过滤：

data ABint = A Int | B Int [A x|A x <- [A 1, B 1, A 2, B 2]] 

求值结果为：

[A 1, A 2] 

序列模式

从上述原始模式，可以建造更加复杂的模式，通常采用的方式，相同于通过组合其他值来建造值。区别在于，具有变量和通配符部份，模式不建造成一个单一值，而是匹配一组值，它们是具体元素和允许在模式结构内变化的元素的组合。

在Haskell和一般的函数式编程语言中，列表是主要数据结构，它通常被定义为一种典型的代数数据类型：

data List a = Nil | Cons a (List a) 

Cons是构造（construct）的简写。很多语言针对以这种方式定义的列表提供特殊语法。例如，Haskell和ML，分别将[]用于Nil，:或::用于Cons，并将方括号用于整个列表。所以Cons 1 (Cons 2 (Cons 3 Nil))通常在Haskell中写为1:2:3:[]或[1,2,3]，在OCaml中写为1::2::3::[]或[1;2;3]。

列表被定义为空列表，或一个元素构造在一个现存的列表上。在Haskell语法下写为：

[] -- 空列表 x:xs -- 元素x构造在列表xs之上 

具有一些元素的一个列表的结构，就是element:list。在模式匹配的时候，断定特定部份的数据等于特定模式。例如，在如下函数中：

head (element:list) = element 

这里断定了head的实际参数的第一个元素被称为element，并且这个函数返回这个元素。之所以知道它是第一个元素的，是因为列表的定义方式，它是一个单一元素构造在一个列表之上，这个单一元素必定是第一个元素。空列表根本不匹配这个模式，因为空列表没有头部（要构造的第一个元素）。

在这个例子中，我们没有用到list，可以漠视它，而将函数写为：

head (element:_) = element 

树状模式

树状模式一般用来匹配由递归数据类型生成的复杂的树状结构，比如编程语言抽象语法树。它通过开始于一个节点，指定某些分支以及节点，并且通过变量或通配符留下一些不指定，来描述一个树的一部份。

下面是在OCaml下，定义一个红黑树和在元素插入后再平衡的函数的例子：

type color = Red | Black type 'a tree = Empty | Tree of color * 'a tree * 'a * 'a tree let rebalance t = match t with | Tree (Black, Tree (Red, Tree (Red, a, x, b), y, c), z, d) | Tree (Black, Tree (Red, a, x, Tree (Red, b, y, c)), z, d) | Tree (Black, a, x, Tree (Red, Tree (Red, b, y, c), z, d)) | Tree (Black, a, x, Tree (Red, b, y, Tree (Red, c, z, d))) -> Tree (Red, Tree (Black, a, x, b), y, Tree (Black, c, z, d)) | _ -> t (* the 'catch-all' case if no previous pattern matches *) 

字符串模式

主条目：正则表达式

迄今最常用形式的模式匹配涉及字符串。在很多编程语言中，使用特定的字符串语法来表示正则表达式，它是描述字符串的模式。

在Haskell中，如下模式匹配有两个字符并且开始于'a'的字符串:

['a', _] 

可以介入符号式实体，来表示一个字符串的很多不同类的有关特征。在Haskell中，可以使用守卫来进行匹配：

[letter, digit] | isAlpha letter && isDigit digit 

它将匹配首个字符是一个字母，接着的是一个数字的字符串。

符号式字符串操纵的主要好处，是它可以与编程语言的其余部份完全的集成，而非成为一个独立的、专用的子单元。这个语言的整体能力，可以放大到建造模式自身，或分析和变换包含它们的程序。

Python的模式匹配

定义

在Python版本3.10中^[15]，模式匹配的语法应该是：

match subject: case <pattern_1>: <action_1> case <pattern_2>: <action_2> case <pattern_3>: <action_3> case _: <action_wildcard> 

其中 subject表示原始数据，<pattern_*>表示不同模式，_表示通配符，如果在上文中没有找到精确匹配的对象，将会使用通配符。如果一个模式匹配没有精确匹配上且没有通配符，整个语句不做任何作用（no-op）。

例子

在Python版本3.10中^[15]：

def http_error(status): match status: case 400: return "Bad request" case 404: return "Not found" case 418: return "I'm a teapot" case _: #省略此行及下一行以创造一个没有通配符的模式匹配 return "Something's wrong with the Internet" 

如果省略最后两行，当status为500时什么都不会发生。

同理，模式匹配也可用于class中：

class Point: x: int y: int def location(point): match point: case Point(x=0, y=0): print("Origin is the point's location.") case Point(x=0, y=y): print(f"Y={y} and the point is on the y-axis.") case Point(x=x, y=0): print(f"X={x} and the point is on the x-axis.") case Point(): print("The point is located somewhere else on the plane.") case _: print("Not a point") 

和其他语言中的模式匹配一样，Python中也可以在匹配的语句中使用通配符：

match test_variable: case ('warning', code, 40): print("A warning has been received.") case ('error', code, _): print(f"An error {code} occurred.") 

引用

1. . [2022-02-18]. （原始内容存档于2021-05-13）. 
2. . [2022-02-18]. （原始内容存档于2022-06-27）. 
3. . [2022-02-18]. （原始内容存档于2022-03-19）. 
4. . docs.python.org. [2021-07-06]. （原始内容存档于2022-06-29）. 
5. . docs.ruby-lang.org. [2021-07-06]. （原始内容存档于2021-12-04）. 
6. . [2022-02-18]. （原始内容存档于2022-05-28）. 
7. . Scala Documentation. [2021-01-17]. （原始内容存档于2022-06-08）. 
8. . [2022-02-18]. （原始内容存档于2022-06-12）. 
9. Turner, D. A. (PDF). [2022-02-18]. （原始内容 (PDF)存档于2020-04-15）. John Darlington’s NPL, “New Programming Language”, developed with Burstall in the period 1973-5, replaced case expressions with multi-equation function definitions over algebraic types, including natural numbers, e.g.
fib (0) <= 1
fib (1) <= 1
fib (n+2) <= fib (n+1) + fib (n)
   Darlington got this idea from Kleene’s recursion equations. 
10. Turner, D. A. (PDF). [2022-02-18]. （原始内容 (PDF)存档于2020-04-15）. Miranda had, instead of conditional expressions, conditional equations with guards. Example:
sign x = 1, if x>0
       = -1, if x<0
       = 0, if x=0
    Combining pattern matching with guards gives a significant gain in expressive power. Guards of this kind first appeared in KRC, “Kent Recursive Calculator”(Turner 1981, 1982), a miniaturised version of SASL which I designed in 1980–81 for teaching. 
11. Warth, Alessandro, and Ian Piumarta. "OMeta: an object-oriented language for pattern matching （页面存档备份，存于互联网档案馆）." Proceedings of the 2007 symposium on Dynamic languages. ACM, 2007.
12. Knuth, Donald E., James H. Morris, Jr, and Vaughan R. Pratt. "Fast pattern matching in strings." SIAM journal on computing 6.2 (1977): 323-350.
13. Joel Moses, "Symbolic Integration", MIT Project MAC MAC-TR-47, December 1967
14. Cantatore, Alessandro. . 2003 [2022-02-18]. （原始内容存档于2020-10-11）. 
15. What's New In Python 3.10 — Python 3.10.0b2 文档. docs.python.org. [2021-06-17]. （原始内容于2021-06-29）. 

外部链接

維基教科書中的相關電子教程：Pattern matching

• Nikolaas N. Oosterhof, Philip K. F. Hölzenspies, and Jan Kuper. . A presentation at Trends in Functional Programming, 2005
• JMatch （页面存档备份，存于互联网档案馆）: the Java programming language extended with pattern matching
• ShowTrend: Online pattern matching for stock prices
• by Dennis Ritchie - provides the history of regular expressions in computer programs
• The Implementation of Functional Programming Languages, pages 53–103 （页面存档备份，存于互联网档案馆） Simon Peyton Jones, published by Prentice Hall, 1987.
• Nemerle, pattern matching （页面存档备份，存于互联网档案馆）.
• Erlang, pattern matching （页面存档备份，存于互联网档案馆）.
• PatMat: a C++ pattern matching library based on （页面存档备份，存于互联网档案馆） SNOBOL/SPITBOL（英语：SPITBOL）
• Temur Kutsia. Flat Matching. Journal of Symbolic Computation 43(12): 858–873. Describes in details flat matching in Mathematica.
• EasyPattern language （页面存档备份，存于互联网档案馆） pattern matching language for non-programmers