跳至內容

模式匹配

本頁使用了標題或全文手工轉換
維基百科，自由的百科全書
  此條目介紹的是函數式程式設計中的模式匹配。關於其他用法，請見「字串搜尋演算法」和「圖型識別」。
  關於在定義要匹配的抽象模式時使用可變的匹配準則，請見「正則表達式」。

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

概述

[編輯]

在一些程式語言中，模式被用作一種通用工具，基於數據的結構來處理數據，包括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. ^ Pattern Matching - C# Guide. [2022-02-18]. （原始內容存檔於2021-05-13）. 
  2. ^ Pattern Matching - F# Guide. [2022-02-18]. （原始內容存檔於2022-06-27）. 
  3. ^ A Gentle Introduction to Haskell: Patterns. [2022-02-18]. （原始內容存檔於2022-03-19）. 
  4. ^ What's New In Python 3.10 — Python 3.10.0b3 documentation. docs.python.org. [2021-07-06]. （原始內容存檔於2022-06-29）. 
  5. ^ pattern_matching - Documentation for Ruby 3.0.0. docs.ruby-lang.org. [2021-07-06]. （原始內容存檔於2021-12-04）. 
  6. ^ Pattern Syntax - The Rust Programming language. [2022-02-18]. （原始內容存檔於2022-05-28）. 
  7. ^ Pattern Matching. Scala Documentation. [2021-01-17]. （原始內容存檔於2022-06-08）. 
  8. ^ Patterns — The Swift Programming Language (Swift 5.1). [2022-02-18]. （原始內容存檔於2022-06-12）. 
  9. ^ 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.     
  10. ^ 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.     
  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. Wildcard matching algorithms. 2003 [2022-02-18]. （原始內容存檔於2020-10-11）. 
  15. ^ 15.0 15.1 What's New In Python 3.10 — Python 3.10.0b2 文档. docs.python.org. [2021-06-17]. （原始內容存檔於2021-06-29）. 

外部連結

[編輯]
維基教科書中的相關電子教學：Pattern matching


取自 "https://zh.wikipedia.org/w/index.php?title=模式匹配&oldid=80877714"