模式匹配

在電腦科學中，**模式匹配**是檢查給定記號序列中，是否存在某種模式的組成部分的行為。與圖型識別相反，匹配通常必須是精確的。模式通常具有序列或樹狀結構的形式。模式匹配的用途包括：輸出一個模式在一個記號序列中的位置（如果有的話），輸出匹配模式的一些組成部份，以及用一些其他的記號序列替換匹配模式（即搜尋和替換）。

## 概述

在一些程式語言中，模式被用作一種通用工具，基於資料的結構來處理資料，包括 C#、 F#、Haskell、ML、Python、Ruby、Rust、Scala、Swift 和 Mathematica 的符號式 Wolfram 語言，它們擁有表達樹狀結構的特殊語法，和基於它的條件執行和值檢索的語言構造。

經常可以給出逐個嘗試的交替式模式，它產生強力的條件編程構造。模式匹配有時包括對守衛子句的支援。

字元序列也就是字串，經常使用正規表示式來描述，並使用像回溯這樣的技術來進行匹配。解析演算法經常依賴模式匹配來將字串變換成語法樹。

## 歷史

具有模式匹配構造的早期程式語言包括：COMIT（1957 年）、SNOBOL（1962 年）、具有樹狀模式的 Refal（1968 年）、Prolog（1972 年）、SASL（1976 年）、NPL（1977 年）和 KRC（1981 年）。

很多文字編輯器支援各種的模式匹配：支援正規表示式尋找的 QED 編輯器，和在尋找中支援 `OR` 運算的某些版本的 TECO。電腦代數系統一般支援在代數表達式上的模式匹配。

## 簡單模式

在模式匹配中，最簡單的模式是一個明確的值或一個變數。例如，考慮採用 Haskell 語法的一個簡單函式，這裡函式參數不放在圓括號內但用空白分隔，`=` 不是賦值而是定義：

這裡的 `0` 是一個單一值模式。只要 `f` 被給予 `0` 作為參數，這個模式就匹配，並且函式返回 `1`。對於任何其他參數，匹配失敗，因而這個函式也失敗。因為在函式定義中，語法上支援交替式模式，可以繼續將定義擴充為接受更一般性的參數：

這裡的第一個 `n` 是單一變數模式，它絕對的匹配任何參數，並將它繫結到名字 `n`，而用在定義的餘下部份之中。在 Haskell 中（至少不似 Hope），模式被依次嘗試，所以第一個定義仍適用於輸入是 `0` 的非常特殊情況，而對於任何其他參數，函式返回 `n * f (n-1)`，具有 `n` 是為參數。

萬用字元模式（通常寫為 `_`）也是簡單的：就像一個變數名字，它匹配任何值，但是不把這個值繫結到任何名字。在簡單字串匹配情況下的匹配萬用字元演算法，已經發展出很多遞迴和非遞迴的變體。

在 Haskell 中，下面的代碼定義了一個代數資料類型 `Color`，它有一個單一的資料構造子 `ColorConstructor`，包裝一個整數和一個字串：

例如，要得到 `Color` 類型的整數部份的一個函式可以寫為：

要得到字串部份：

這些函式可以通過 Haskell 的資料記錄語法自動建立。

模式匹配還可應用來過濾特定結構的資料。例如，在 Haskell 中可以使用列表推導式進行這種過濾：

求值結果為：

## 序列模式

從上述原始模式，可以建造更加複雜的模式，通常採用的方式，相同於通過組合其他值來建造值。區別在於，具有變數和萬用字元部份，模式不建造成一個單一值，而是匹配一組值，它們是具體元素和允許在模式結構內變化的元素的組合。

在 Haskell 和一般的函式語言程式設計語言中，列表是主要資料結構，它通常被定義為一種典型的代數資料類型：

`Cons` 是構造（**cons**truct）的簡寫。很多語言針對以這種方式定義的列表提供特殊語法。例如，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 語法下寫為：

具有一些元素的一個列表的結構，就是 `element:list`。在模式匹配的時候，斷定特定部份的資料等於特定模式。例如，在如下函式中：

這裡斷定了 `head` 的實際參數的第一個元素被稱為 `element`，並且這個函式返回這個元素。之所以知道它是第一個元素的，是因為列表的定義方式，它是一個單一元素構造在一個列表之上，這個單一元素必定是第一個元素。空串列根本不匹配這個模式，因為空串列沒有頭部（要構造的第一個元素）。

在這個例子中，我們沒有用到 `list`，可以漠視它，而將函式寫為：

## 樹狀模式

樹狀模式一般用來匹配由遞迴資料類型生成的複雜的樹狀結構，比如程式語言抽象語法樹。它通過開始於一個節點，指定某些分支以及節點，並且通過變數或萬用字元留下一些不指定，來描述一個樹的一部份。

下面是在 OCaml 下，定義一個紅黑樹和在元素插入後再平衡的函式的例子：

## 字串模式

迄今最常用形式的模式匹配涉及字串。在很多程式語言中，使用特定的字串語法來表示正規表示式，它是描述字串的模式。

在 Haskell 中，如下模式匹配有兩個字元並且開始於 `'a'` 的字串:

可以介入符號式實體，來表示一個字串的很多不同類的有關特徵。在 Haskell 中，可以使用守衛來進行匹配：

它將匹配首個字元是一個字母，接著的是一個數字的字串。

符號式字串操縱的主要好處，是它可以與程式語言的其餘部份完全的整合，而非成為一個獨立的、專用的子單元。這個語言的整體能力，可以放大到建造模式自身，或分析和變換包含它們的程式。

## Python 的模式匹配

### 定義

在 Python 版本 3.10 中，模式匹配的語法應該是：

其中 `subject` 表示原始資料，`<pattern_*>` 表示不同模式，`_` 表示萬用字元，如果在上文中沒有找到精確匹配的物件，將會使用萬用字元。如果一個模式匹配沒有精確匹配上且沒有萬用字元，整個語句不做任何作用（no-op）。

### 例子

在 Python 版本 3.10 中：

如果省略最後兩行，當 `status` 為 500 時什麼都不會發生。

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

和其他語言中的模式匹配一樣，Python 中也可以在匹配的語句中使用萬用字元：

## 參照

## 外部連結

* 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