JSRUN 用代码说话

模式匹配

编辑教程

模式匹配

定义函数

关键字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)

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

JSRUN闪电教程系统是国内最先开创的教程维护系统, 所有工程师都可以参与共同维护的闪电教程,让知识的积累变得统一完整、自成体系。 大家可以一起参与进共编,让零散的知识点帮助更多的人。
X
支付宝
9.99
无法付款,请点击这里
金额: 0
备注:
转账时请填写正确的金额和备注信息,到账由人工处理,可能需要较长时间
如有疑问请联系QQ:565830900
正在生成二维码, 此过程可能需要15秒钟