# 模式匹配

## 简单模式

```f 0 = 1
```

```f n = n * f (n-1)
```

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

```data Color = ColorConstructor Integer String
```

```integerPart (ColorConstructor theInteger _) = theInteger
```

```stringPart (ColorConstructor _ theString) = theString
```

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

```[A 1, A 2]
```

## 序列模式

```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]`

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

```head (element:list) = element
```

```head (element:_) = element
```

## 树状模式

```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', _]
```

```[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>
```

### 例子

Python版本3.10中[15]

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

```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")
```

```match test_variable:
case ('warning', code, 40):
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) <= 1fib (1) <= 1fib (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. What's New In Python 3.10 — Python 3.10.0b2 文档. docs.python.org. [2021-06-17]. （原始内容存档于2021-06-29）.