模式匹配

模式匹配

定义函数

关键字function可用于在function的最后一个参数上启动模式匹配。例如，我们可以编写一个名为sum的函数，它以这种方式计算整数列表的总和

let rec sum = function
  | [] -> 0
  | h::t -> h + sum t
;;

val sum : int list -> int = <fun>

使用模式匹配的因子函数

let rec factorial n = match n with
| 0 | 1 -> 1
| n -> n * (factorial (n - 1))

此函数匹配值0和1，并将它们映射到递归定义的基本情况。然后所有其他数字映射到此函数的递归调用。

匹配记录字段

模式匹配可用于解构记录。我们用表示文本文件中位置的记录类型来说明这一点， 例如程序的源代码。

type location = {
  filename : string;
  line: int;
  column: int;
  offset: int;
}

可以解构类型位置的值x ，如下所示：

let { filename; line; column; offset; } = x

类似的语法可用于定义函数，例如打印位置的函数：

let print_location { filename; line; column; offset; } =
  Printf.printf "%s: %d: %d" filename line column

或者

let print_location = function { filename; line; column; offset; } ->
  Printf.printf "%s: %d: %d" filename line column\

匹配记录的模式不需要提及记录的所有字段。由于该函数不使用offset字段，我们可以将其删除：

let print_location { filename; line; column; } =
  Printf.printf "%s: %d: %d" filename line column

在模块中定义记录时，足以限定模式中出现的第一个字段：

module Location =
struct
  type t = {
      filename : string;
      line: int;
      column: int;
      offset: int;
    }
end

let print_location { Location.filename; line; column; } =
  Printf.printf "%s: %d: %d" filename line column

否定正常形式：深度模式匹配

模式匹配允许解构复杂值，并且它决不限于值的表示的“最外层”级别。为了说明这一点，我们实现了将布尔表达式转换为布尔表达式的函数，其中所有否定仅在原子上，所谓的否定正规形式和以这种形式识别表达式的谓词：

我们定义布尔表达式的类型，其原子由字符串标识为

type expr =
| Atom of string
| Not of expr
| And of expr * expr
| Or of expr * expr

让我们首先定义一个以否定正规形式识别表达式的谓词：

let rec is_nnf = function
| (Atom(_) | Not(Atom(_))) -> true
| Not(_) -> false
| (And(expr1, expr2) | Or(expr1, expr2)) -> is_nnf expr1 && is_nnf expr2

如您所见，可以匹配嵌套模式，如Not(Atom(_)) 。现在我们实现一个函数，将布尔表达式映射为否定正规形式的等效布尔表达式：

let rec nnf = function
| (Atom(_) | Not(Atom(_))) as expr -> expr
| Not(And(expr1, expr2)) -> Or(nnf(Not(expr1)),nnf(Not(expr2)))
| Not(Or(expr1, expr2)) -> And(nnf(Not(expr1)),nnf(Not(expr2)))
| And(expr1, expr2) -> And(nnf expr1, nnf expr2)
| Or(expr1, expr2) -> Or(nnf expr1, nnf expr2)
| Not(Not(expr)) -> nnf expr

第二个函数更多地使用了嵌套模式。我们最终可以在对含义的否定中测试我们的代码：

# let impl a b =
Or(Not(a), b);;
  val impl : expr -> expr -> expr = <fun>
# let expr = Not(impl (Atom "A") (Atom "B"));;
val expr : expr = Not (Or (Not (Atom "A"), Atom "B"))
# nnf expr;;
- : expr = And (Atom "A", Not (Atom "B"))
# is_nnf (nnf expr);;
- : bool = true

OCaml类型系统能够验证模式匹配的穷举性。例如，如果我们在nnf函数中省略了Not(Or(expr1, expr2))情况，编译器会发出警告：

# let rec non_exhaustive_nnf = function
| (Atom(_) | Not(Atom(_))) as expr -> expr
| Not(And(expr1, expr2)) -> Or(nnf(Not(expr1)),nnf(Not(expr2)))
| And(expr1, expr2) -> And(nnf expr1, nnf expr2)
| Or(expr1, expr2) -> Or(nnf expr1, nnf expr2)
| Not(Not(expr)) -> nnf expr;;
          Characters 14-254:
  ..............function
  | (Atom(_) | Not(Atom(_))) as expr -> expr
  | Not(And(expr1, expr2)) -> Or(nnf(Not(expr1)),nnf(Not(expr2)))
  | And(expr1, expr2) -> And(nnf expr1, nnf expr2)
  | Or(expr1, expr2) -> Or(nnf expr1, nnf expr2)
  | Not(Not(expr)) -> nnf expr..
Warning 8: this pattern-matching is not exhaustive.
Here is an example of a case that is not matched:
Not (Or (_, _))
val non_exhaustive_nnf : expr -> expr = <fun>

（在调用编译器或解释器时，可以将此警告视为-w @8选项的错误。）

此功能可提高编译器接受的程序的安全性和正确性。然而，它具有其他用途，并且可以例如用于探索性编程。将转换写入普通表单非常有趣，从处理简单案例的函数的原始版本开始，并使用编译器提供的非匹配案例的示例来优化处理。

评估布尔表达式

我们定义布尔表达式的类型，其原子由字符串标识为

type expr =
| Atom of string
| Not of expr
| And of expr * expr
| Or of expr * expr

并且可以使用oracle : string -> bool评估这些表达式oracle : string -> bool给出我们找到的原子的值如下：

let rec eval oracle = function
| Atom(name) -> oracle name
| Not(expr) -> not(eval oracle expr)
| And(expr1, expr2) -> (eval oracle expr1) && (eval oracle expr2)
| Or(expr1, expr2)  -> (eval oracle expr1) || (eval oracle expr2)

了解该功能如何清晰易读。由于正确使用模式匹配，读取此功能的程序员只需要很少的时间来确保正确实现。