模式匹配
![本頁使用了標題或全文手工轉換](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
在電腦科學中,模式匹配是檢查給定記號序列中,是否存在某種模式的組成部分的行為。與圖型識別相反,匹配通常必須是精確的。模式通常具有序列或樹狀結構的形式。模式匹配的用途包括:輸出一個模式在一個記號序列中的位置(如果有的話),輸出匹配模式的一些組成部份,以及用一些其他的記號序列替換匹配模式(即搜尋和替換)。
概述
在一些程式語言中,模式被用作一種通用工具,基於數據的結構來處理數據,包括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).
外部連結
![](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/f/fa/Wikibooks-logo.svg/40px-Wikibooks-logo.svg.png)
- 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
|
|
|