模式匹配
在计算机科学中,模式匹配是检查给定记号序列中,是否存在某种模式的组成部分的行为。与模式识别相反,匹配通常必须是精确的。模式通常具有序列或树状结构的形式。模式匹配的用途包括:输出一个模式在一个记号序列中的位置(如果有的话),输出匹配模式的一些组成部份,以及用一些其他的记号序列替换匹配模式(即搜索和替换)。
概述
编辑在一些编程语言中,模式被用作一种通用工具,基于数据的结构来处理数据,包括C#[1]、 F#[2]、Haskell[3]、ML、Python[4]、Ruby[5]、Rust[6]、Scala[7]、Swift[8]和Mathematica的符号式Wolfram语言,它们拥有表达树状结构的特殊语法,和基于它的条件执行和值检索的语言构造。
经常可以给出逐个尝试的交替式模式,它产生强力的条件编程构造[9]。模式匹配有时包括对守卫子句的支持[10]。
字符序列也就是字符串,经常使用正则表达式来描述,并使用像回溯这样的技术来进行匹配。解析算法经常依赖模式匹配来将字符串变换成语法树[11][12]。
历史
编辑具有模式匹配构造的早期编程语言包括:COMIT(1957年)、SNOBOL(1962年)、具有树状模式的Refal(1968年)、Prolog(1972年)、SASL(1976年)、NPL(1977年)和KRC(1981年)。
很多文本编辑器支持各种的模式匹配:支持正则表达式查找的QED编辑器,和在查找中支持OR
运算的某些版本的TECO。计算机代数系统一般支持在代数表达式上的模式匹配[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
是为参数。
通配符模式(通常写为_
)也是简单的:就像一个变量名字,它匹配任何值,但是不把这个值绑定到任何名字。在简单字符串匹配情况下的匹配通配符算法,已经发展出很多递归和非递归的变体[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)。
例子
编辑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.")
引用
编辑- ^ Pattern Matching - C# Guide. [2022-02-18]. (原始内容存档于2021-05-13).
- ^ Pattern Matching - F# Guide. [2022-02-18]. (原始内容存档于2022-06-27).
- ^ A Gentle Introduction to Haskell: Patterns. [2022-02-18]. (原始内容存档于2022-03-19).
- ^ What's New In Python 3.10 — Python 3.10.0b3 documentation. docs.python.org. [2021-07-06]. (原始内容存档于2022-06-29).
- ^ pattern_matching - Documentation for Ruby 3.0.0. docs.ruby-lang.org. [2021-07-06]. (原始内容存档于2021-12-04).
- ^ Pattern Syntax - The Rust Programming language. [2022-02-18]. (原始内容存档于2022-05-28).
- ^ Pattern Matching. Scala Documentation. [2021-01-17]. (原始内容存档于2022-06-08).
- ^ Patterns — The Swift Programming Language (Swift 5.1). [2022-02-18]. (原始内容存档于2022-06-12).
- ^ Turner, D. A. Some History of Functional Programming Languages (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. - ^ Turner, D. A. Some History of Functional Programming Languages (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. - ^ Warth, Alessandro, and Ian Piumarta. "OMeta: an object-oriented language for pattern matching (页面存档备份,存于互联网档案馆)." Proceedings of the 2007 symposium on Dynamic languages. ACM, 2007.
- ^ 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.
- ^ Joel Moses, "Symbolic Integration", MIT Project MAC MAC-TR-47, December 1967
- ^ Cantatore, Alessandro. Wildcard matching algorithms. 2003 [2022-02-18]. (原始内容存档于2020-10-11).
- ^ 15.0 15.1 What's New In Python 3.10 — Python 3.10.0b2 文档. docs.python.org. [2021-06-17]. (原始内容存档于2021-06-29).
外部链接
编辑- Nikolaas N. Oosterhof, Philip K. F. Hölzenspies, and Jan Kuper. Application patterns. A presentation at Trends in Functional Programming, 2005
- JMatch (页面存档备份,存于互联网档案馆): the Java programming language extended with pattern matching
- ShowTrend: Online pattern matching for stock prices
- An incomplete history of the QED Text Editor 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 (页面存档备份,存于互联网档案馆).
- Prop: a C++ based pattern matching language, 1999
- PatMat: a C++ pattern matching library based on (页面存档备份,存于互联网档案馆) SNOBOL/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