Course Builder个人学习工作台 · 本地模式
OCaml：从类型推导到可测试的命令行工具

11 · 递归类型：实现一个小型规则求值器

目标：定义可以嵌套的筛选规则，并用递归函数解释其含义。

列表是一种递归数据结构，但并非所有问题都是线性的。例如筛选条件“主题是 OCaml，并且不少于 30 分钟”有两个子条件；将来还能把这个整体与另一个条件组合。把规则写成字符串会引入解析问题，把规则直接写成递归 variant 则能先专注于含义。

And of rule * rule 表示一个节点携带两条子规则；类型定义中的 rule 指回正在定义的类型。一个值可以是一棵树。求值器跟随树结构：叶子检查记录，组合节点递归检查子节点。

这是独立的语言拓展实验，帮助你理解 AST、表达式解释器等 OCaml 常见应用。StudyLog 命令行不需要加入这套规则语言，完成本课也不需要学习字符串解析器。

实验：数据描述规则，函数赋予含义

创建 rules.ml：

type session = { topic : string; minutes : int }
type rule =
  | Topic of string
  | At_least of int
  | And of rule * rule
  | Or of rule * rule

let rec matches rule session =
  match rule with
  | Topic name -> session.topic = name
  | At_least minimum -> session.minutes >= minimum
  | And (left, right) -> matches left session && matches right session
  | Or (left, right) -> matches left session || matches right session

let () =
  let rule = And (Topic "OCaml", At_least 30) in
  let first = { topic = "OCaml"; minutes = 25 } in
  let second = { topic = "OCaml"; minutes = 35 } in
  Printf.printf "%b %b\n" (matches rule first) (matches rule second);
  assert (matches (Or (Topic "Types", rule)) second)

%b 打印布尔值。&& 与 || 使用短路求值：左边已经决定结果时，右边不执行。先画出 And 节点下面的两个叶子，预测两个记录各自在哪个叶子失败，再运行：

ocaml rules.ml

预期输出：

false true

first 的主题符合，但时长不足；second 同时满足两个条件。规则是一份普通数据，可以在多个记录上重复使用；函数则解释这份数据。区分数据与解释器，是把一连串硬编码条件变成可组合模型的关键。

本例对有限规则树求值，递归走向更小的子树。它不是尾递归遍历所有分支；极深的人工构造规则仍可能耗尽栈。不要把入门示例扩展成无限深输入处理器后沿用相同假设。

新增一个构造器，让检查器指路

  1. 把 And 改成 Or，两个结果都会为真。
  2. 将规则改成 And (Topic "Types", At_least 30)，两个结果都为假；同步修改或临时去掉最后的断言，避免它仍按旧规则验收。
  3. 恢复主示例，开始下面的独立扩展。

独立练习：增加 Not of rule，表达不满足某条规则。检查 Not (Topic "Rust") 接受 OCaml 记录，双重否定保持原结果。

参考修改与验收

在 rule 定义中增加 | Not of rule，在 matches 中增加 | Not inner -> not (matches inner session)。然后追加：

let () =
  let sample = { topic = "OCaml"; minutes = 35 } in
  assert (matches (Not (Topic "Rust")) sample);
  assert (not (matches (Not (Topic "OCaml")) sample));
  assert (matches (Not (Not (At_least 30))) sample =
          matches (At_least 30) sample);
  print_endline "rule checks passed"

这是基于主示例的修改。断言必须在添加构造器与求值分支后才能编译。

若新增类型后看到非穷尽匹配，检查所有解释该类型的函数；不要直接补 _ -> false，那会掩盖你尚未定义新规则语义的事实。若程序无法编译且说构造器需要两个参数，检查是否把 And (left, right) 写成了 And left right。

参考资料