第 9 章：命令式编程（Imperative Programming）

原文：Anil Madhavapeddy and Yaron Minsky, Real World OCaml: Functional Programming for the Masses, Second Edition, Chapter 9。维护者已确认本书为开源书籍，可翻译并发布用于学习研究。本章包含 Jason Hickey 的贡献。

到目前为止，本书展示的大多数代码，实际上也是大多数 OCaml 代码，都是纯的（pure）。纯代码不会修改程序的内部状态，不会执行 I/O，不会读取时钟，也不会以其他方式与世界中可变的部分交互。因此，纯函数的行为就像数学函数：给定相同输入，总是返回相同结果；除了返回计算值之外，不会影响外部世界。另一方面，命令式（imperative）代码通过副作用运行，这些副作用会修改程序的内部状态，或与外部世界交互。命令式函数每次被调用时都会产生新的效果，并且可能返回不同结果。

纯代码是 OCaml 的默认方式，而且理由充分：它通常更容易推理、更不容易出错，也更容易组合。但命令式代码对任何实用编程语言都至关重要，因为真实世界的任务要求你与外部世界交互，而外部世界本质上就是命令式的。命令式编程对性能也可能很重要。虽然 OCaml 中的纯代码效率很高，但有许多算法只有使用命令式技术才能高效实现。

OCaml 在这里提供了一种愉快的折中：它让用纯风格编程变得简单自然，同时也为命令式编程提供了强大支持。本章会带你了解 OCaml 的命令式特性，并帮助你充分利用它们。

9.1 示例：命令式字典（Example: Imperative Dictionaries）

我们从实现一个简单的命令式字典开始，也就是从键到值的可变映射。这是一个玩具实现，确实不适合真实世界使用。没关系，因为 Base 和标准库都提供了有效的命令式字典。关于如何使用 Base 的实现，第 15 章“映射与哈希表（Maps and Hash Tables）”会给出更多建议。

我们现在描述的字典，和 Base 与标准库中的字典一样，会实现为哈希表。具体来说，我们会使用一种开放哈希（open hashing）方案：哈希表是一个桶数组，每个桶包含一个键/值对列表，这些键/值对都被哈希到该桶中。

下面是我们要满足的签名，它写在接口文件 dictionary.mli 中。类型 ('a, 'b) t 表示一个字典，其中键的类型为 'a，数据的类型为 'b。

open Base

type ('a, 'b) t

val create
  :  hash:('a -> int)
  -> equal:('a -> 'a -> bool)
  -> ('a, 'b) t

val length : ('a, 'b) t -> int
val add : ('a, 'b) t -> key:'a -> data:'b -> unit
val find : ('a, 'b) t -> 'a -> 'b option
val iter : ('a, 'b) t -> f:(key:'a -> data:'b -> unit) -> unit
val remove : ('a, 'b) t -> 'a -> unit

这个 mli 也包含一组辅助函数；从它们的名字和类型签名中，大体可以推断其目的和行为。注意，create 函数接收用于哈希键和测试键相等性的函数作为参数。

你可能会注意到，有些函数（如 add 和 iter）返回 unit。这在函数式代码中并不常见，但对命令式函数来说很常见，因为这类函数的主要目的通常是改变某个数据结构，而不是计算一个值。

现在我们逐段看它的实现，也就是对应的 ml 文件 dictionary.ml。我们会在遇到不同命令式构造时顺便解释它们。

第一步，是把字典类型定义为一条记录。

open Base

type ('a, 'b) t =
  { mutable length : int
  ; buckets : ('a * 'b) list array
  ; hash : 'a -> int
  ; equal : 'a -> 'a -> bool
  }

第一个字段 length 被声明为可变。在 OCaml 中，记录默认不可变，但单个字段在标记为 mutable 时就是可变的。第二个字段 buckets 本身不可变，但它包含一个数组，而数组自身是一种可变数据结构。其余字段保存哈希和相等性检查函数。

接下来开始组合操纵字典的基本函数：

let num_buckets = 17
let hash_bucket t key = t.hash key % num_buckets

let create ~hash ~equal =
  { length = 0
  ; buckets = Array.create ~len:num_buckets []
  ; hash
  ; equal
  }

let length t = t.length

let find t key =
  List.find_map
    t.buckets.(hash_bucket t key)
    ~f:(fun (key', data) ->
      if t.equal key' key then Some data else None)

注意，num_buckets 是一个常量，这意味着我们的桶数组长度固定。实际实现需要随着字典元素数量增长而扩展数组，但为了简化讲解，这里省略了这一点。

hash_bucket 函数会在模块其余部分反复使用，用来为给定键选择它应该存储在数组中的位置。

上面定义的其他函数相当直接：

create : 创建一个空字典。

length : 从对应记录字段中取出长度，也就是返回字典中存储的条目数量。

find : 在表中查找匹配键，如果找到就以 option 形式返回对应值。

find 中还出现了一段重要的命令式语法：我们写 array.(index) 来从数组中取值。find 还使用了 List.find_map，你可以在顶层输入它来查看类型：

# open Base;;
# List.find_map;;
- : 'a list -> f:('a -> 'b option) -> 'b option = <fun>

List.find_map 会遍历列表元素，对每个元素调用 f，直到 f 返回 Some，这时返回其中的值。如果 f 对所有值都返回 None，则最终返回 None。

现在来看 iter 的实现：

let iter t ~f =
  for i = 0 to Array.length t.buckets - 1 do
    List.iter t.buckets.(i) ~f:(fun (key, data) -> f ~key ~data)
  done

iter 用于遍历字典中的所有条目。具体来说，iter t ~f 会对字典 t 中的每个键/值对调用 f。注意，f 必须返回 unit，因为预期它通过副作用工作，而不是通过返回值工作；整体 iter 函数也返回 unit。

iter 的代码使用了两种迭代形式：一个 for 循环用于遍历桶数组；在该循环内部，再调用 List.iter 遍历某个桶中的值。我们也可以用递归函数代替外层 for 循环，但 for 循环在语法上很方便，在命令式上下文中也更熟悉、更符合惯用法。

下面的代码用于向字典添加映射，以及从字典中移除映射：

let bucket_has_key t i key =
  List.exists t.buckets.(i) ~f:(fun (key', _) -> t.equal key' key)

let add t ~key ~data =
  let i = hash_bucket t key in
  let replace = bucket_has_key t i key in
  let filtered_bucket =
    if replace
    then
      List.filter t.buckets.(i) ~f:(fun (key', _) ->
          not (t.equal key' key))
    else t.buckets.(i)
  in
  t.buckets.(i) <- (key, data) :: filtered_bucket;
  if not replace then t.length <- t.length + 1

let remove t key =
  let i = hash_bucket t key in
  if bucket_has_key t i key
  then (
    let filtered_bucket =
      List.filter t.buckets.(i) ~f:(fun (key', _) ->
          not (t.equal key' key))
    in
    t.buckets.(i) <- filtered_bucket;
    t.length <- t.length - 1)

前面的代码变复杂，是因为我们需要检测自己是在覆盖已有绑定，还是在删除已有绑定，从而决定是否需要修改 t.length。辅助函数 bucket_has_key 就用于这个目的。

add 和 remove 中还出现了另一段语法：使用 <- 运算符更新数组元素（array.(i) <- expr），以及更新记录字段（record.field <- expression）。

我们还使用 ;，也就是顺序执行运算符，来表达一串命令式动作。也可以用 let 绑定完成同样的事：

  let () = t.buckets.(i) <- (key, data) :: filtered_bucket in
  if not replace then t.length <- t.length + 1

但 ; 更简洁，也更符合惯用法。更一般地说，

<expr1>;
<expr2>;
...
<exprN>

等价于

let () = <expr1> in
let () = <expr2> in
...
<exprN>

对顺序表达式 expr1; expr2 求值时，会先求值 expr1，再求值 expr2。表达式 expr1 应该具有 unit 类型（不过这只是警告，而非硬性限制；编译器标志 -strict-sequence 会把它变成硬性限制，通常这是个好主意），而 expr2 的值会作为整个顺序表达式的值返回。例如，顺序表达式 print_string "hello world"; 1 + 2 会先打印字符串 "hello world"，然后返回整数 3。

还要注意，我们把所有产生副作用的操作都放在每个函数的最后。这样做是良好实践，因为它最小化了这些操作被异常中断的机会，避免数据结构停留在不一致状态。

9.2 原始可变数据（Primitive Mutable Data）

现在已经看过一个完整例子，我们来更系统地观察 OCaml 中的命令式编程。前面遇到了两种不同形式的可变数据：带可变字段的记录和数组。现在我们会更详细讨论它们，以及 OCaml 中可用的其他原始可变数据形式。

9.2.1 类数组数据（Array-Like Data）

OCaml 支持多种类数组数据结构，也就是可变的、以整数为索引的容器，并且能以常量时间访问元素。本节会讨论其中几种。

9.2.1.1 普通数组（Ordinary arrays）

array 类型用于通用的多态数组。Array 模块提供了多种与数组交互的工具函数，其中包括不少会改变数组的操作。例如，Array.set 用于设置单个元素，Array.blit 用于高效地把一段索引范围内的值复制到另一段范围。

数组还带有特殊语法，用于从数组中取出元素：

<array_expr>.(<index_expr>)

以及用于设置数组中的元素：

<array_expr>.(<index_expr>) <- <value_expr>

数组越界访问（实际上所有类数组数据结构的越界访问）都会导致抛出异常。

数组字面量用 [| 和 |] 作为定界符。因此，[| 1; 2; 3 |] 是一个整数数组字面量。

9.2.1.2 bytes 与 string（bytes and strings）

到目前为止我们遇到的字符串本质上是字节数组，并且最常用于文本数据。你可以想象用 char array 达成同样目的（char 表示一个 8 位字符），但字符串在空间上高效得多；在 64 位机器上，array 会用一个 8 字节字来存储单个条目，而字符串每个字符只用一个字节。

不过，与数组不同，字符串是不可变的。有时，拥有一种空间高效、可变的字节数组会很方便。好在 OCaml 通过 bytes 类型提供了这一点。

可以使用 Bytes.set 设置单个字符，并且 bytes 类型的值可以与 string 类型相互转换。

# let b = Bytes.of_string "foobar";;
val b : bytes = "foobar"
# Bytes.set b 0 (Char.uppercase (Bytes.get b 0));;
- : unit = ()
# Bytes.to_string b;;
- : string = "Foobar"

9.2.1.3 Bigarray（Bigarrays）

Bigarray.t 是对 OCaml 堆外某块内存的句柄。它们主要用于与 C 或 Fortran 库交互，第 24 章“值的内存表示（Memory Representation of Values）”会讨论。Bigarray 也有自己的取值和赋值语法：

<bigarray_expr>.{<index_expr>}
<bigarray_expr>.{<index_expr>} <- <value_expr>

9.2.2 可变记录字段、对象字段与 ref 单元（Mutable Record and Object Fields and Ref Cells）

正如我们已经看到的，记录默认不可变，但单个记录字段可以声明为可变。这些可变字段可以用 <- 运算符设置，即 record.field <- expr。

第 13 章“对象（Objects）”会看到，对象字段同样可以声明为可变，然后用与记录字段大体相同的方式修改。

9.2.2.1 ref 单元（Ref cells）

OCaml 中的变量永远不可变：它们可以指向可变数据，但变量本身指向的东西不能改变。不过，有时候你确实想做其他语言中可变变量会做的事：定义一个单一的可变值。在 OCaml 中，这通常通过 ref 实现；ref 本质上是一个带有单个多态可变字段的容器。

ref 类型的定义如下：

# type 'a ref = { mutable contents : 'a };;
type 'a ref = { mutable contents : 'a; }

标准库定义了以下运算符来处理 ref：

ref expr : 构造一个引用单元，其中包含表达式 expr 定义的值。

!refcell : 返回引用单元的内容。

refcell := expr : 替换引用单元的内容。

可以看到它们的实际用法：

# let x = ref 1;;
val x : int ref = {Base.Ref.contents = 1}
# !x;;
- : int = 1
# x := !x + 1;;
- : unit = ()
# !x;;
- : int = 2

前面这些只是普通 OCaml 函数，可以像下面这样定义：

# let ref x = { contents = x };;
val ref : 'a -> 'a ref = <fun>
# let (!) r = r.contents;;
val ( ! ) : 'a ref -> 'a = <fun>
# let (:=) r x = r.contents <- x;;
val ( := ) : 'a ref -> 'a -> unit = <fun>

这反映了一个事实：ref 单元其实只是可变记录字段的一个特例。

9.2.3 外部函数（Foreign Functions）

OCaml 中命令式操作的另一个来源，是通过 OCaml 外部函数接口（FFI）与外部库交互所得到的资源。FFI 让 OCaml 能够访问由系统调用或其他外部库导出的命令式构造。其中许多是内置的，比如访问 write 系统调用或 clock；另一些来自用户库。第 23 章“外部函数接口（Foreign Function Interface）”会更详细讨论 OCaml 的 FFI。

9.3 for 与 while 循环（For and While Loops）

OCaml 支持传统命令式循环构造，尤其是 for 和 while 循环。严格来说，这两种构造都不是必要的，因为它们可以用递归函数模拟。尽管如此，在命令式编程时，显式的 for 与 while 循环都更简洁，也更符合惯用法。

for 循环是两者中更简单的一个。实际上，我们已经看过 for 循环的使用：Dictionary 中的 iter 函数就是用它构建的。下面是一个简单的 for 例子。注意，我们打开 Stdio 库，以便访问 printf 函数。

# open Stdio;;
# for i = 0 to 3 do printf "i = %d\n" i done;;
i = 0
i = 1
i = 2
i = 3
- : unit = ()

可以看到，上下边界都是包含的。也可以用 downto 沿另一个方向迭代：

# for i = 3 downto 0 do printf "i = %d\n" i done;;
i = 3
i = 2
i = 1
i = 0
- : unit = ()

注意，for 循环的循环变量（这里是 i）在循环作用域内不可变，并且也局部于该循环，也就是说，循环外不能引用它。

OCaml 也支持 while 循环，它包含一个条件和一个循环体。循环会先求值条件；如果条件求值得到 true，就求值循环体，然后重新开始循环。下面是一个就地反转数组的简单函数：

# let rev_inplace ar =
    let i = ref 0 in
    let j = ref (Array.length ar - 1) in
    (* terminate when the upper and lower indices meet *)
    while !i < !j do
      (* swap the two elements *)
      let tmp = ar.(!i) in
      ar.(!i) <- ar.(!j);
      ar.(!j) <- tmp;
      (* bump the indices *)
      Int.incr i;
      Int.decr j
    done;;
val rev_inplace : 'a array -> unit = <fun>
# let nums = [|1;2;3;4;5|];;
val nums : int array = [|1; 2; 3; 4; 5|]
# rev_inplace nums;;
- : unit = ()
# nums;;
- : int array = [|5; 4; 3; 2; 1|]

在前面的例子中，我们使用了 Int.incr 和 Int.decr，它们是内置函数，分别用于把一个 int ref 加一和减一。

9.4 示例：双向链表（Example: Doubly Linked Lists）

另一个常见的命令式数据结构是双向链表。双向链表可以沿两个方向遍历，并且可以用常量时间向列表添加元素或从列表移除元素。Core 定义了一个双向链表（模块名为 Doubly_linked），但为了说明问题，我们会定义自己的链表库。

下面是我们要构建的模块的 mli：

open Base

type 'a t
type 'a element

(** Basic list operations *)

val create : unit -> 'a t
val is_empty : 'a t -> bool

(** Navigation using [element]s *)

val first : 'a t -> 'a element option
val next : 'a element -> 'a element option
val prev : 'a element -> 'a element option
val value : 'a element -> 'a

(** Whole-data-structure iteration *)

val iter : 'a t -> f:('a -> unit) -> unit
val find_el : 'a t -> f:('a -> bool) -> 'a element option

(** Mutation *)

val insert_first : 'a t -> 'a -> 'a element
val insert_after : 'a element -> 'a -> 'a element
val remove : 'a t -> 'a element -> unit

注意，这里定义了两种类型：'a t 是列表类型；'a element 是元素类型。元素充当指向列表内部的指针，允许我们在列表中导航，并给我们一个应用可变操作的位置。

现在来看实现。先定义 'a element 和 'a t：

open Base

type 'a element =
  { value : 'a
  ; mutable next : 'a element option
  ; mutable prev : 'a element option
  }

type 'a t = 'a element option ref

'a element 是一条记录，包含要存储在节点中的值，以及指向前一个和下一个元素的可选（且可变）字段。在列表开头，prev 字段为 None；在列表末尾，next 字段为 None。

列表本身的类型 'a t 是一个可变引用，指向一个可选 element。如果列表为空，该引用为 None；否则为 Some。

现在可以定义几个操作列表和元素的基本函数：

let create () = ref None
let is_empty t = Option.is_none !t
let value elt = elt.value
let first t = !t
let next elt = elt.next
let prev elt = elt.prev

这些函数都能相当直接地从类型定义推导出来。

9.4.1 循环数据结构（Cyclic Data Structures）

双向链表是一种循环数据结构，意思是存在一串非平凡的指针路径，可以沿着它们最终回到自身。一般来说，构建循环数据结构需要使用副作用。这通常通过先构造数据元素，然后再用赋值添加循环来完成。

不过有一个例外：可以用 let rec 构造固定大小的循环数据结构：

# let rec endless_loop = 1 :: 2 :: 3 :: endless_loop;;
val endless_loop : int list = [1; 2; 3; <cycle>]

然而，这种方法相当有限。通用循环数据结构需要可变性。

9.4.2 修改列表（Modifying the List）

现在开始考虑会改变列表的操作。先从 insert_first 开始，它会把一个元素插入到列表前端：

let insert_first t value =
  let new_elt = { prev = None; next = !t; value } in
  (match !t with
  | Some old_first -> old_first.prev <- Some new_elt
  | None -> ());
  t := Some new_elt;
  new_elt

insert_first 先定义一个新元素 new_elt，然后把它链接到列表中，最后设置列表本身，使其指向 new_elt。注意，match 表达式的优先级很低，所以为了把它与后续赋值（t := Some new_elt）分开，我们给 match 加上了括号。也可以用 begin ... end 达成同样目的；如果没有某种括号，最后的赋值会被错误地当成 None 分支的一部分。

可以用 insert_after 在列表后面的位置插入元素。insert_after 接收两个参数：一个 element，新节点要插入在它之后；以及要插入的值：

let insert_after elt value =
  let new_elt = { value; prev = Some elt; next = elt.next } in
  (match elt.next with
  | Some old_next -> old_next.prev <- Some new_elt
  | None -> ());
  elt.next <- Some new_elt;
  new_elt

还需要一个 remove 函数：

let remove t elt =
  let { prev; next; _ } = elt in
  (match prev with
  | Some prev -> prev.next <- next
  | None -> t := next);
  (match next with
  | Some next -> next.prev <- prev
  | None -> ());
  elt.prev <- None;
  elt.next <- None

注意，前面的代码很谨慎：如果后一个元素存在，就修改它的 prev 指针；如果前一个元素存在，就修改它的 next 指针。如果不存在前一个元素，就更新列表指针本身。无论如何，元素自身的 next 和 prev 指针都会被设置为 None。

这些函数比看上去更脆弱。特别是，接口误用可能导致数据损坏。例如，对同一个元素执行两次删除，会导致主列表引用被设置为 None，从而清空列表。从元素并不属于的列表中移除元素，也会产生类似问题。

这并不意外。复杂的命令式数据结构可能相当棘手，远比它们的纯版本更难处理。前面描述的问题可以通过更仔细的错误检测来处理，而像 Core 的 Doubly_linked 这样的模块已经处理了这些错误校正。在可以使用设计良好的库时，应当使用其中的命令式数据结构。不能这样做时，就应格外注意错误处理。

9.4.3 迭代函数（Iteration Functions）

定义列表、字典、树等容器时，通常会想定义一组迭代函数，例如 iter、map 和 fold，用来简洁表达常见迭代模式。

Dlist 有两个这样的迭代器：iter 的目标是按顺序对列表的每个元素调用一个产生 unit 的函数；find_el 会对每个存储在列表中的值运行给定测试函数，并返回第一个通过测试的 element。iter 和 find_el 都使用简单的递归循环实现，这些循环通过 next 从元素走到元素，并通过 value 从给定节点提取元素值：

let iter t ~f =
  let rec loop = function
    | None -> ()
    | Some el ->
      f (value el);
      loop (next el)
  in
  loop !t

let find_el t ~f =
  let rec loop = function
    | None -> None
    | Some elt -> if f (value elt) then Some elt else loop (next elt)
  in
  loop !t

这样，我们的实现就完成了。但要做出真正可用的双向链表，还有相当多工作要做。如前所述，你大概最好使用 Core 的 Doubly_linked 这类模块；它接口更完整，也处理了更多棘手边界情况。尽管如此，这个例子应该足以展示在 OCaml 中构建非平凡命令式数据结构可以使用的一些技术，以及其中的一些陷阱。

9.5 惰性与其他良性副作用（Laziness and Other Benign Effects）

有很多情况下，你基本上想用纯风格编程，但又希望有限地使用副作用来提升代码性能。这类副作用有时称为良性副作用（benign effects），它们能让你利用 OCaml 的命令式特性，同时仍保留纯编程的大部分好处。

最简单的良性副作用之一是惰性（laziness）。惰性值在真正需要之前不会被计算。在 OCaml 中，惰性值用 lazy 关键字创建；它可以把任意类型为 s 的表达式转换为类型为 s lazy_t 的惰性值。对该表达式的求值会被推迟，直到用 Lazy.force 强制求值：

# let v = lazy (print_endline "performing lazy computation"; Float.sqrt 16.);;
val v : float lazy_t = <lazy>
# Lazy.force v;;
performing lazy computation
- : float = 4.
# Lazy.force v;;
- : float = 4.

从 print 语句可以看出，实际计算只执行了一次，并且只在调用 force 后执行。

为了更好理解惰性的工作方式，我们来逐步实现自己的惰性类型。先声明表示惰性值的类型：

# type 'a lazy_state =
    | Delayed of (unit -> 'a)
    | Value of 'a
    | Exn of exn;;
type 'a lazy_state = Delayed of (unit -> 'a) | Value of 'a | Exn of exn
# type 'a our_lazy = { mutable state : 'a lazy_state };;
type 'a our_lazy = { mutable state : 'a lazy_state; }

lazy_state 表示惰性值的可能状态。惰性值在运行前处于 Delayed 状态，其中 Delayed 保存一个函数，用于计算相关值。惰性值被强制求值并且计算正常结束后，会处于 Value 状态。Exn 情况表示惰性值已经被强制求值，但计算以异常结束。惰性值只是一个记录，里面有一个可变字段保存 lazy_state；这个可变性让它可以从 Delayed 状态转变为 Value 或 Exn 状态。

可以从 thunk 创建惰性值，也就是从接收 unit 参数的函数创建惰性值。把表达式包进 thunk，是暂停表达式计算的另一种方式：

# let our_lazy f = { state = Delayed f };;
val our_lazy : (unit -> 'a) -> 'a our_lazy = <fun>
# let v =
    our_lazy (fun () ->
      print_endline "performing lazy computation"; Float.sqrt 16.);;
val v : float our_lazy = {state = Delayed <fun>}

现在只需要一种强制惰性值求值的方法。下面的函数正是用于此目的。

# let our_force l =
    match l.state with
    | Value x -> x
    | Exn e -> raise e
    | Delayed f ->
      try
        let x = f () in
        l.state <- Value x;
        x
      with exn ->
        l.state <- Exn exn;
        raise exn;;
val our_force : 'a our_lazy -> 'a = <fun>

它的使用方式和 Lazy.force 一样：

# our_force v;;
performing lazy computation
- : float = 4.
# our_force v;;
- : float = 4.

我们的惰性实现与内置版本之间最主要的用户可见差异是语法。内置的 lazy 允许我们直接写 lazy (sqrt 16.)，而不必写 our_lazy (fun () -> sqrt 16.)，从而避免显式声明函数。

9.5.1 记忆化与动态规划（Memoization and Dynamic Programming）

另一种良性副作用是记忆化（memoization）。记忆化函数会记住先前调用的结果；当再次给出相同参数时，就能直接返回结果，而不必重新计算。

下面的函数接收任意单参数函数，并返回它的记忆化版本。这里我们使用 Base 的 Hashtbl 模块，而不是前面的玩具 Dictionary。

这个实现需要一个 Hashtbl.Key.t 参数，它扮演了 Dictionary 中 hash 和 equal 的角色。Hashtbl.Key.t 是所谓一等模块的一个例子，第 12 章“一等模块（First-Class Modules）”会看到更多相关内容。

# let memoize m f =
    let memo_table = Hashtbl.create m in
    (fun x ->
       Hashtbl.find_or_add memo_table x ~default:(fun () -> f x));;
val memoize : 'a Hashtbl.Key.t -> ('a -> 'b) -> 'a -> 'b = <fun>

前面的代码有点微妙。memoize 接收函数 f 作为参数，然后分配一个多态哈希表（名为 memo_table），并返回一个新函数，也就是 f 的记忆化版本。调用这个新函数时，它会使用 Hashtbl.find_or_add 尝试在 memo_table 中查找值；如果查找失败，就调用 f 并存储结果。注意，memo_table 会被该函数引用，所以直到 memoize 返回的函数本身被回收，它都不会被回收。

当某个函数重新计算成本很高，并且你不介意无限期缓存旧值时，记忆化很有用。一个重要警告是：记忆化函数本质上会泄漏内存。只要持有记忆化函数，就会持有它到目前为止返回过的所有结果。

记忆化对于高效实现某些递归算法也很有用。一个很好的例子是计算两个字符串之间编辑距离（edit distance，也叫 Levenshtein 距离）的算法。编辑距离是把一个字符串转换为另一个字符串所需的单字符修改次数，包括字母替换、插入和删除。这类距离度量可以用于多种近似字符串匹配问题，例如拼写检查器。

考虑下面用于计算编辑距离的代码。这里并不要求理解算法，但请注意递归调用的结构：

# let rec edit_distance s t =
    match String.length s, String.length t with
    | (0,x) | (x,0) -> x
    | (len_s,len_t) ->
      let s' = String.drop_suffix s 1 in
      let t' = String.drop_suffix t 1 in
      let cost_to_drop_both =
        if Char.(=) s.[len_s - 1] t.[len_t - 1] then 0 else 1
      in
      List.reduce_exn ~f:Int.min
        [ edit_distance s' t  + 1
        ; edit_distance s  t' + 1
        ; edit_distance s' t' + cost_to_drop_both
        ];;
val edit_distance : string -> string -> int = <fun>
# edit_distance "OCaml" "ocaml";;
- : int = 2

需要注意的是，如果调用 edit_distance "OCaml" "ocaml"，它会进一步派发以下调用：

这些调用又会进一步派发其他调用：

可以看到，有些调用是重复的。例如，有两个不同的调用都会调用 edit_distance "OCam" "oca"。冗余调用的数量会随着字符串大小指数级增长，这意味着我们的 edit_distance 实现对较大字符串来说慢得惊人。可以使用 Core 的 Time 模块写一个小计时函数来观察这一点。

# let time f =
    let open Core in
    let start = Time.now () in
    let x = f () in
    let stop = Time.now () in
    printf "Time: %F ms\n" (Time.diff stop start |> Time.Span.to_ms);
    x;;
val time : (unit -> 'a) -> 'a = <fun>

现在可以用它试几个例子：

# time (fun () -> edit_distance "OCaml" "ocaml");;
Time: 0.655651092529 ms
- : int = 2
# time (fun () -> edit_distance "OCaml 4.13" "ocaml 4.13");;
Time: 2541.6533947 ms
- : int = 2

仅仅多了几个字符，就让它慢了几千倍！

记忆化在这里会有巨大帮助，但要修复这个问题，我们需要记忆化 edit_distance 对自身发出的调用。这种递归记忆化与一种常见算法技术密切相关，叫作动态规划（dynamic programming）。不同之处在于，动态规划会自底向上完成必要子计算，提前准备以后可能需要的值；递归记忆化则自顶向下，只在发现需要某个子计算时才执行它。

为了看看怎么做，先离开 edit_distance，考虑一个简单得多的例子：计算 Fibonacci 序列第 n 个元素。Fibonacci 序列按定义以两个 1 开头，之后每个元素都是前两个元素之和。Fibonacci 的经典递归定义如下：

# let rec fib i =
  if i <= 1 then i else fib (i - 1) + fib (i - 2);;
val fib : int -> int = <fun>

然而，这个定义是指数级慢的，原因和 edit_distance 很像：最终会对 fib 进行许多冗余调用。性能上可以很明显地看到这一点：

# time (fun () -> fib 20);;
Time: 1.14369392395 ms
- : int = 6765
# time (fun () -> fib 40);;
Time: 14752.7184486 ms
- : int = 102334155

可以看到，fib 40 的计算时间比 fib 20 长了数千倍。

那么，如何用记忆化让它更快？棘手之处在于，我们需要在 fib 内部的递归调用之前插入记忆化。不能只是用普通方式定义 fib，然后事后对它记忆化，并指望第一次调用 fib 就得到改善。

# let fib = memoize (module Int) fib;;
val fib : int -> int = <fun>
# time (fun () -> fib 40);;
Time: 18174.5970249 ms
- : int = 102334155
# time (fun () -> fib 40);;
Time: 0.00524520874023 ms
- : int = 102334155

为了让 fib 变快，第一步是以一种展开递归的方式重写 fib。下面这个版本把一个函数（也叫 fib）作为第一个参数，并会用它来代替通常的递归调用。

# let fib_norec fib i =
    if i <= 1 then i
    else fib (i - 1) + fib (i - 2);;
val fib_norec : (int -> int) -> int -> int = <fun>

现在可以通过打结（tying the recursive knot）把它变回普通 Fibonacci 函数：

# let rec fib i = fib_norec fib i;;
val fib : int -> int = <fun>
# fib 20;;
- : int = 6765

我们甚至可以写一个多态函数 make_rec，用于为任何这种形式的函数打递归结：

# let make_rec f_norec =
    let rec f x = f_norec f x in
    f;;
val make_rec : (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b = <fun>
# let fib = make_rec fib_norec;;
val fib : int -> int = <fun>
# fib 20;;
- : int = 6765

这是一段相当奇怪的代码，可能需要想一会儿才能看清发生了什么。和 fib_norec 一样，传给 make_rec 的函数 f_norec 不是递归函数，但它接收一个自己将调用的函数作为参数。make_rec 做的事，本质上是把 f_norec 喂给它自己，从而让它成为真正的递归函数。

这已经足够巧妙，但我们真正做到的只是找到了一种新方式来实现同一个旧的、很慢的 Fibonacci 函数。要让它更快，需要一个 make_rec 的变体，在打递归结时插入记忆化。我们把这个函数叫作 memo_rec：

# let memo_rec m f_norec x =
    let fref = ref (fun _ -> assert false) in
    let f = memoize m (fun x -> f_norec !fref x) in
    fref := f;
    f x;;
val memo_rec : 'a Hashtbl.Key.t -> (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b =
  <fun>

注意，memo_rec 的签名几乎和 make_rec 一样。

这里我们使用引用来打递归结，而不是使用 let rec；稍后会解释为什么 let rec 在这里不行。

使用 memo_rec，现在可以构建一个高效版本的 fib：

# let fib = memo_rec (module Int) fib_norec;;
val fib : int -> int = <fun>
# time (fun () -> fib 40);;
Time: 0.121355056763 ms
- : int = 102334155

可以看到，指数时间复杂度消失了。

这里的内存行为很重要。回头看 memo_rec 的定义会发现，调用 memo_rec fib_norec 并不会触发对 memoize 的调用。只有在调用 fib、从而向 memo_rec 提供最后一个参数时，memoize 才会被调用。该调用的结果会在 fib 调用返回后离开作用域，所以对某个函数调用 memo_rec 不会造成内存泄漏：记忆化表会在计算完成后被回收。

可以把 memo_rec 放在单个声明中使用，让它看起来几乎只是 let rec 的一种特殊形式：

# let fib = memo_rec (module Int) (fun fib i ->
  if i <= 1 then 1 else fib (i - 1) + fib (i - 2));;
val fib : int -> int = <fun>

用记忆化实现 Fibonacci 有点过度，而且上面定义的 fib 也不是特别高效，会分配与传入数字线性相关的空间。要写一个只用常量空间的 Fibonacci 函数并不难。

但记忆化很适合优化 edit_distance，我们可以在这里应用处理 fib 时的同样方法。需要把 edit_distance 改成接收一对字符串作为单个参数，因为 memo_rec 只适用于单参数函数。（可以随时用一个包装函数恢复原来的接口。）仅仅做这个修改，并加上 memo_rec 调用，就能得到一个记忆化版本的 edit_distance。记忆化键会是一对字符串，所以我们需要拿到一个具备必要功能的模块，用于在 Base 中构建哈希表。

手写哈希函数、相等性测试之类很乏味，也容易出错，因此我们改用几个不同的语法扩展，自动派生必要功能。启用 ppx_jane 会引入一组这样的派生器，下面定义 String_pair 时会用到其中三个。

# #require "ppx_jane";;
# module String_pair = struct
    type t = string * string [@@deriving sexp_of, hash, compare]
  end;;
module String_pair :
  sig
    type t = string * string
    val sexp_of_t : t -> Sexp.t
    val hash_fold_t : Hash.state -> t -> Hash.state
    val hash : t -> int
    val compare : t -> t -> int
  end

有了它，就能定义优化后的 edit_distance。

# let edit_distance = memo_rec (module String_pair)
    (fun edit_distance (s,t) ->
       match String.length s, String.length t with
       | (0,x) | (x,0) -> x
       | (len_s,len_t) ->
         let s' = String.drop_suffix s 1 in
         let t' = String.drop_suffix t 1 in
         let cost_to_drop_both =
           if Char.(=) s.[len_s - 1] t.[len_t - 1] then 0 else 1
         in
         List.reduce_exn ~f:Int.min
           [ edit_distance (s',t ) + 1
           ; edit_distance (s ,t') + 1
           ; edit_distance (s',t') + cost_to_drop_both
  ]);;
val edit_distance : String_pair.t -> int = <fun>

这个新版 edit_distance 比最初版本高效得多；下面这个调用比没有记忆化时快了许多千倍。

# time (fun () -> edit_distance ("OCaml 4.09","ocaml 4.09"));;
Time: 0.964403152466 ms
- : int = 2

9.5.1.1 let rec 的限制（Limitations of let rec）

你可能会想知道，为什么我们没有像早先对 make_rec 那样，在 memo_rec 中用 let rec 打递归结。下面这段代码尝试这样做：

# let memo_rec m f_norec =
    let rec f = memoize m (fun x -> f_norec f x) in
    f;;
Line 2, characters 17-49:
Error: This kind of expression is not allowed as right-hand side of `let rec'

OCaml 拒绝这个定义，是因为作为严格语言，OCaml 对 let rec 右侧能放什么有限制。具体来说，想象下面的代码片段会如何编译：

let rec x = x + 1

注意，x 是普通值，而不是函数。因此，编译器不清楚应该如何处理这个定义。你可以想象它被编译成一个无限循环，但 x 的类型是 int，而不存在一个对应无限循环的 int。因此，这个构造实际上不可能被编译。

为了避免这类不可能的情况，编译器只允许三种构造出现在 let rec 的右侧：函数定义、构造器，或 lazy 关键字。这排除了一些合理的东西，比如我们的 memo_rec 定义，但也阻止了没有意义的东西，比如前面的 x 定义。

值得注意的是，这些限制不会出现在 Haskell 这样的惰性语言中。事实上，如果使用 OCaml 的惰性，也可以让类似 x 的定义成立：

# let rec x = lazy (force x + 1);;
val x : int lazy_t = <lazy>

当然，真的尝试计算它会失败。当一个惰性值在自身求值过程中试图强制自身求值时，OCaml 的 lazy 会抛出异常。

# force x;;
Exception: Lazy.Undefined.

但也可以用 lazy 创建有用的递归定义。特别是，可以用惰性让 memo_rec 的定义在没有显式可变性的情况下工作：

# let lazy_memo_rec m f_norec x =
    let rec f = lazy (memoize m (fun x -> f_norec (force f) x)) in
    (force f) x;;
val lazy_memo_rec : 'a Hashtbl.Key.t -> (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b =
  <fun>
# time (fun () -> lazy_memo_rec (module Int) fib_norec 40);;
Time: 0.181913375854 ms
- : int = 102334155

惰性比显式可变性更受约束，因此在某些情况下，它能产生更容易推理其行为的代码。

9.6 输入与输出（Input and Output）

命令式编程不只是修改内存中的数据结构。任何不能归结为“从参数到返回值的确定性转换”的函数，本质上都是命令式的。这不仅包括改变程序数据的东西，也包括与程序外部世界交互的操作。这类交互的一个重要例子是 I/O，也就是读写文件、终端输入输出和网络套接字等对象的操作。

OCaml 中有多个 I/O 库。本节会讨论 OCaml 的缓冲 I/O 库，它可以通过 Stdio 中的 In_channel 和 Out_channel 模块使用。其他 I/O 原语也可以通过 Core 中的 Unix 模块以及异步 I/O 库 Async 获得；第 17 章“使用 Async 的并发编程（Concurrent Programming with Async）”会介绍 Async。Core 的 In_channel 与 Out_channel（以及 Core 的 Unix 模块）中的大多数功能都来自标准库，但这里会使用 Core 的接口。

9.6.1 终端 I/O（Terminal I/O）

OCaml 的缓冲 I/O 库围绕两种类型组织：in_channel，用于读取的通道；以及 out_channel，用于写入的通道。In_channel 和 Out_channel 模块只直接支持对应文件和终端的通道；其他类型的通道可以通过 Unix 模块创建。

先从终端开始讨论 I/O。遵循 UNIX 模型，与终端的通信围绕三个通道组织，它们对应 Unix 中的三个标准文件描述符：

In_channel.stdin : “标准输入”通道。默认情况下，输入来自终端，终端处理键盘输入。

Out_channel.stdout : “标准输出”通道。默认情况下，写入 stdout 的输出会显示在用户终端上。

Out_channel.stderr : “标准错误”通道。它类似于 stdout，但用于错误消息。

stdin、stdout 和 stderr 这些值足够有用，所以它们也直接出现在 Core 命名空间的顶层，不必通过 In_channel 和 Out_channel 模块访问。

来看一个简单交互式应用。下面的程序 time_converter 会提示用户输入时区，然后打印该时区中的当前时间。这里使用 Core 的 Zone 模块查找时区，并使用 Time 模块计算当前时间，然后按相关时区打印：

open Core

let () =
  Out_channel.output_string stdout "Pick a timezone: ";
  Out_channel.flush stdout;
  match In_channel.(input_line stdin) with
  | None -> failwith "No timezone provided"
  | Some zone_string ->
    let zone = Time_unix.Zone.find_exn zone_string in
    let time_string = Time.to_string_abs (Time.now ()) ~zone in
    Out_channel.output_string stdout
      (String.concat
         ["The time in ";Time_unix.Zone.to_string zone;" is ";time_string;".\n"]);
    Out_channel.flush stdout

可以使用 dune 构建并运行这个程序，不过你需要像第 5 章“文件、模块与程序（Files, Modules, and Programs）”中所述那样添加 dune-project 和 dune 文件。会看到它提示你输入：

$ dune exec ./time_converter.exe
Pick a timezone:

然后可以输入时区名称并按下回车，它会打印出该时区的当前时间：

Pick a timezone: Europe/London
The time in Europe/London is 2013-08-15 00:03:10.666220+01:00.

我们在 stdout 上调用了 Out_channel.flush，因为 out_channel 是缓冲的。也就是说，OCaml 不会在你每次调用 output_string 时都立即执行一次写入。相反，写入会被缓冲，直到写入内容足够多、触发缓冲刷新，或直到显式请求刷新。这样可以减少系统调用数量，从而大幅提升写入过程的效率。

注意，In_channel.input_line 返回 string option，其中 None 表示输入流已经结束（也就是遇到文件结束条件）。Out_channel.output_string 用于打印最终输出，而 Out_channel.flush 被调用以把输出刷新到屏幕。最后一次刷新严格来说不是必需的，因为程序在该指令后结束，此时剩余输出无论如何都会被刷新；但显式刷新仍然是良好实践。

9.6.2 使用 printf 格式化输出（Formatted Output with printf）

使用 Out_channel.output_string 这类函数生成输出简单易懂，但可能有点冗长。OCaml 也支持使用 printf 函数进行格式化输出，它以 C 标准库中的 printf 为模型。printf 接收一个格式字符串（format string），描述要打印什么以及如何格式化，并接收要打印的参数；这些参数由嵌入格式字符串中的格式化指令决定。例如，可以写：

# printf
    "%i is an integer, %F is a float, \"%s\" is a string\n"
  3 4.5 "five";;
3 is an integer, 4.5 is a float, "five" is a string
- : unit = ()

与 C 的 printf 不同，OCaml 中的 printf 是类型安全的。具体来说，如果提供的参数类型与格式字符串中的内容不匹配，就会得到类型错误：

# printf "An integer: %i\n" 4.5;;
Line 1, characters 27-30:
Error: This expression has type float but an expression was expected of type
         int

9.6.2.1 理解格式字符串（Understanding Format Strings）

printf 使用的格式字符串与普通字符串非常不同。这一区别与 OCaml 的 printf 功能（不同于 C 中的等价物）是类型安全的有关。具体来说，编译器会检查格式字符串提到的类型是否与传给 printf 的其余参数类型匹配。

为了进行检查，OCaml 需要在编译时分析格式字符串的内容，这意味着格式字符串必须作为字符串字面量在编译时可得。事实上，如果尝试把普通字符串传给 printf，编译器会报错：

# let fmt = "%i is an integer\n";;
val fmt : string = "%i is an integer\n"
# printf fmt 3;;
Line 1, characters 8-11:
Error: This expression has type string but an expression was expected of type
         ('a -> 'b, Stdio.Out_channel.t, unit) format =
           ('a -> 'b, Stdio.Out_channel.t, unit, unit, unit, unit) format6

如果 OCaml 推断某个字符串字面量是格式字符串，就会在编译时把它解析为格式字符串，并根据找到的格式化指令选择其类型。因此，如果添加类型注解，表明正在定义的字符串实际是格式字符串，它就会被按格式字符串解释。（这里打开 CamlinternalFormatBasics，这样打印出来的格式字符串表示不会占满整页。）

# open CamlinternalFormatBasics;;
# let fmt : ('a, 'b, 'c) format =
  "%i is an integer\n";;
val fmt : (int -> 'c, 'b, 'c) format =
  Format
   (Int (Int_i, No_padding, No_precision,
     String_literal (" is an integer\n", End_of_format)),
   "%i is an integer\n")

相应地，可以把它传给 printf：

# printf fmt 3;;
3 is an integer
- : unit = ()

如果这看起来和你到目前为止见过的其他所有东西都不同，那是因为它确实不同。这实际上是类型系统中的一个特殊情况。大多数时候，你不需要理解格式字符串的这种特殊处理；只要使用 printf，不必担心细节即可。不过，把这个故事的大致轮廓放在脑后仍然很有用。

现在来看如何用 printf 把时间转换程序改写得更简洁：

open Core

let () =
  printf "Pick a timezone: %!";
  match In_channel.input_line In_channel.stdin with
  | None -> failwith "No timezone provided"
  | Some zone_string ->
    let zone = Time_unix.Zone.find_exn zone_string in
    let time_string = Time.to_string_abs (Time.now ()) ~zone in
    printf "The time in %s is %s.\n%!" (Time_unix.Zone.to_string zone) time_string

在前面的例子中，我们只使用了两个格式化指令：%s 用于包含字符串，%! 让 printf 刷新通道。

printf 的格式化指令提供了大量控制能力，可以指定诸如以下内容：

• 对齐与填充

• 字符串的转义规则

• 数字应格式化为十进制、十六进制还是二进制

• 浮点转换的精度

也有一些 printf 风格函数以 stdout 之外的输出为目标，包括：

• eprintf，打印到 stderr

• fprintf，打印到任意 out_channel

• sprintf，返回格式化后的字符串

所有这些，以及更多内容，都可以在 OCaml 手册中 Printf 模块的 API 文档里找到。

9.6.3 文件 I/O（File I/O）

in_channel 和 out_channel 的另一个常见用途，是处理文件。下面是一对函数：一个创建装满数字的文件，另一个读取这样的文件并返回这些数字的和：

# let create_number_file filename numbers =
    let outc = Out_channel.create filename in
    List.iter numbers ~f:(fun x -> Out_channel.fprintf outc "%d\n" x);
    Out_channel.close outc;;
val create_number_file : string -> int list -> unit = <fun>
# let sum_file filename =
    let file = In_channel.create filename in
    let numbers = List.map ~f:Int.of_string (In_channel.input_lines file) in
    let sum = List.fold ~init:0 ~f:(+) numbers in
    In_channel.close file;
    sum;;
val sum_file : string -> int = <fun>
# create_number_file "numbers.txt" [1;2;3;4;5];;
- : unit = ()
# sum_file "numbers.txt";;
- : int = 15

对这两个函数，我们都遵循相同的基本顺序：先创建通道，然后使用通道，最后关闭通道。关闭通道很重要，因为如果不关闭，就不会把与该文件相关的资源释放回操作系统。

前面代码的一个问题是，如果它在工作过程中抛出异常，实际上不会关闭文件。如果尝试读取一个实际不包含数字的文件，就会看到这样的错误：

# sum_file "/etc/hosts";;
Exception:
(Failure
  "Int.of_string: \"127.0.0.1   localhost localhost.localdomain localhost4 localhost4.localdomain4\"")

如果在循环中一遍又一遍这样做，最终会耗尽文件描述符：

# for i = 1 to 10000 do try ignore (sum_file "/etc/hosts") with _ -> () done;;
- : unit = ()
# sum_file "numbers.txt";;
Error: I/O error: ...: Too many open files

这时，如果还想打开更多文件，就需要重启顶层了！

为了避免这种情况，需要确保代码会在结束后清理自身。可以使用第 8 章“错误处理（Error Handling）”中描述的 protect 函数，如下所示：

# let sum_file filename =
    let file = In_channel.create filename in
    Exn.protect ~f:(fun () ->
      let numbers = List.map ~f:Int.of_string (In_channel.input_lines file) in
      List.fold ~init:0 ~f:(+) numbers)
      ~finally:(fun () -> In_channel.close file);;
val sum_file : string -> int = <fun>

现在，文件描述符泄漏消失了：

# for i = 1 to 10000 do try ignore (sum_file "/etc/hosts" : int) with _ -> () done;;
- : unit = ()
# sum_file "numbers.txt";;
- : int = 15

这其实展示了命令式编程和异常之间更一般的问题。如果你正在改变程序内部状态，而这个过程被异常中断，就需要非常仔细地考虑从当前状态继续工作是否安全。

In_channel 有一些函数可以自动处理部分细节。例如，In_channel.with_file 接收一个文件名和一个处理 in_channel 数据的函数，并负责打开和关闭文件相关的记账工作。可以用这个函数改写 sum_file，如下所示：

# let sum_file filename =
    In_channel.with_file filename ~f:(fun file ->
      let numbers = List.map ~f:Int.of_string (In_channel.input_lines file) in
      List.fold ~init:0 ~f:(+) numbers);;
val sum_file : string -> int = <fun>

我们这个 sum_file 实现还有另一个缺点：它会先把整个文件读入内存再处理。对于大文件，更高效的方式是一行一行处理。可以用 In_channel.fold_lines 做到这一点：

# let sum_file filename =
    In_channel.with_file filename ~f:(fun file ->
      In_channel.fold_lines file ~init:0 ~f:(fun sum line ->
        sum + Int.of_string line));;
val sum_file : string -> int = <fun>

这只是 In_channel 和 Out_channel 功能的一点尝试。要获得更完整的理解，应该阅读 API 文档。

9.7 求值顺序（Order of Evaluation）

表达式的求值顺序是编程语言定义中的重要组成部分，在命令式编程时尤其重要。你可能遇到过的大多数编程语言都是严格的（strict），OCaml 也是如此。在严格语言中，当把某个标识符绑定到某个表达式的结果时，会先对表达式求值，然后再绑定变量。类似地，如果用一组参数调用函数，这些参数会先被求值，然后再传给函数。

考虑下面这个简单例子。这里有一组角度，我们想判断其中是否有某个角的 sin 为负。下面的代码片段可以回答这个问题：

# let x = Float.sin 120. in
  let y = Float.sin 75.  in
  let z = Float.sin 128. in
  List.exists ~f:(fun x -> Float.O.(x < 0.)) [x;y;z];;
- : bool = true

从某种意义上说，我们并不真的需要计算 sin 128，因为 sin 75 已经是负数，所以甚至在计算 sin 128 之前就能知道答案。

事情不必如此。使用 lazy 关键字，可以把原始计算写成一种不会计算 sin 128 的形式：

# let x = lazy (Float.sin 120.) in
  let y = lazy (Float.sin 75.)  in
  let z = lazy (Float.sin 128.) in
  List.exists ~f:(fun x -> Float.O.(Lazy.force x < 0.)) [x;y;z];;
- : bool = true

可以通过几处恰当放置的 printf 确认这一点：

# let x = lazy (printf "1\n"; Float.sin 120.) in
  let y = lazy (printf "2\n"; Float.sin 75.)  in
  let z = lazy (printf "3\n"; Float.sin 128.) in
  List.exists ~f:(fun x -> Float.O.(Lazy.force x < 0.)) [x;y;z];;
1
2
- : bool = true

OCaml 默认严格，是有充分理由的：惰性求值和命令式编程通常并不搭配，因为惰性会让推理某个副作用何时发生变得更困难。理解副作用的顺序，是推理命令式程序行为的关键。

因为 OCaml 是严格的，所以我们知道，一串 let 绑定所绑定的表达式会按照它们定义的顺序求值。但单个表达式内部的求值顺序呢？正式答案是：表达式内部的求值顺序未定义。在实践中，OCaml 只有一个编译器，其行为是一种事实上的标准。不幸的是，这种情况下的求值顺序通常与人们可能期望的相反。

考虑下面的例子：

# List.exists ~f:(fun x -> Float.O.(x < 0.))
    [ (printf "1\n"; Float.sin 120.);
      (printf "2\n"; Float.sin 75.);
      (printf "3\n"; Float.sin 128.); ];;
3
2
1
- : bool = true

这里可以看到，最后出现的子表达式实际上最先被求值！这对许多不同种类的表达式来说通常都是如此。如果想确保不同子表达式的求值顺序，应当把它们表达为一系列 let 绑定。

9.8 副作用与弱多态（Side Effects and Weak Polymorphism）

考虑下面这个简单的命令式函数：

# let remember =
    let cache = ref None in
    (fun x ->
       match !cache with
       | Some y -> y
       | None -> cache := Some x; x);;
val remember : '_weak1 -> '_weak1 = <fun>

remember 只是缓存传给它的第一个值，然后在每次调用时都返回那个值。这是因为 cache 只创建并初始化一次，而且会在 remember 的多次调用之间共享。

remember 并不是一个特别有用的函数，但它提出了一个有趣问题：它应该具有什么类型？

第一次调用时，remember 返回传入它的同一个值，这意味着它的输入类型和返回类型应该相同。因此，remember 应该具有某种类型 t -> t。remember 中没有任何东西把 t 的选择绑定到某个特定类型，所以你可能期望 OCaml 会泛化，把 t 替换为一个多态类型变量。正是这种泛化首先给了我们多态类型。举例来说，恒等函数就是这样得到多态类型的：

# let identity x = x;;
val identity : 'a -> 'a = <fun>
# identity 3;;
- : int = 3
# identity "five";;
- : string = "five"

可以看到，identity 的多态类型允许它作用于不同类型的值。

但 remember 并不是这样。从前面的例子可以看到，OCaml 为 remember 推断出的类型看起来几乎像恒等函数的类型，但又不完全一样。再看一次：

val remember : '_weak1 -> '_weak1 = <fun>

类型变量 '_weak1 中的下划线告诉我们，该变量只是弱多态的（weakly polymorphic），也就是说，它可以与任意一个单一类型一起使用。这是合理的，因为与 identity 不同，remember 总是返回第一次调用时传给它的值，这意味着它的返回值必须始终具有同一类型。

只要 OCaml 获得线索，知道弱多态变量应该作为哪种具体类型使用，它就会把该变量转换为具体类型：

# let remember_three () = remember 3;;
val remember_three : unit -> int = <fun>
# remember;;
- : int -> int = <fun>
# remember "avocado";;
Line 1, characters 10-19:
Error: This expression has type string but an expression was expected of type
         int

注意，remember 的类型被 remember_three 的定义确定了，即使 remember_three 从未被调用！

9.8.1 值限制（The Value Restriction）

那么，编译器什么时候会推断弱多态类型？如前所见，当未知类型的值被存入持久可变单元中时，我们需要弱多态类型。因为类型系统不够精确，无法判断所有可能发生这种事的情况，OCaml 使用一个粗略规则来标记那些不会引入任何持久可变单元的情况，并且只在这些情况下推断多态类型。这个规则称为值限制（value restriction）。

值限制的核心观察是：有些表达式，我们称之为简单值（simple values），从本质上不可能引入持久可变单元，包括：

• 常量，例如整数和浮点字面量

• 只包含其他简单值的构造器

• 函数声明，也就是以 fun 或 function 开头的表达式，或者等价的 let 绑定 let f x = ...

• 形如 let var = expr1 in expr2 的 let 绑定，其中 expr1 和 expr2 都是简单值

因此，下面的表达式是简单值，所以其中包含的值类型可以是多态的：

# (fun x -> [x;x]);;
- : 'a -> 'a list = <fun>

但如果写下一个按前面定义并非简单值的表达式，就会得到不同结果。

# identity (fun x -> [x;x]);;
- : '_weak2 -> '_weak2 list = <fun>

原则上，在这里推断出完全多态变量是安全的；但由于 OCaml 的类型系统不区分纯函数和非纯函数，它无法区分这两种情况。

值限制并不要求没有可变状态，只要求没有能够在同一函数多次使用之间共享值的持久可变状态。因此，每次调用时都产生新引用的函数可以具有完全多态类型：

# let f () = ref None;;
val f : unit -> 'a option ref = <fun>

但像 memoize 这种拥有跨调用持久存在的可变缓存的函数，只能是弱多态的。

9.8.2 部分应用与值限制（Partial Application and the Value Restriction）

大多数时候，值限制生效是有充分理由的，也就是说，因为相关值实际上只能安全地与单一类型一起使用。但有时候，值限制会在你不希望它生效时生效。最常见的这类情况是部分应用函数。部分应用函数和任何函数应用一样，不是简单值，因此由部分应用创建的函数有时会比你预期的泛化程度更低。

考虑 List.init 函数，它用于创建列表，列表中每个元素都通过对该元素索引调用一个函数而创建：

# List.init;;
- : int -> f:(int -> 'a) -> 'a list = <fun>
# List.init 10 ~f:Int.to_string;;
- : string list = ["0"; "1"; "2"; "3"; "4"; "5"; "6"; "7"; "8"; "9"]

假设我们想创建一个 List.init 的专门版本，它总是创建长度为 10 的列表。可以用部分应用做到这一点：

# let list_init_10 = List.init 10;;
val list_init_10 : f:(int -> '_weak3) -> '_weak3 list = <fun>

可以看到，现在为得到的函数推断出了弱多态类型。这是因为没有任何东西保证 List.init 不会在内部创建某个持久 ref，并在多次调用 list_init_10 之间共享。可以通过避免部分应用来消除这种可能性，同时让编译器推断出多态类型：

# let list_init_10 ~f = List.init 10 ~f;;
val list_init_10 : f:(int -> 'a) -> 'a list = <fun>

这种变换称为 eta 展开（eta expansion），它经常用于解决值限制带来的问题。

9.8.3 放宽值限制（Relaxing the Value Restriction）

OCaml 实际上比前面暗示的更擅长推断多态类型。我们所描述的值限制基本上是一种语法检查：可以做几类算作简单值的操作，而任何简单值都可以被泛化。

但 OCaml 实际上有一个放宽版本的值限制，可以利用类型信息，让一些并非简单值的东西也获得多态类型。

例如，我们已经看到函数应用，即便是恒等函数的简单应用，也不是简单值，因此可能把多态值变成弱多态值：

# identity (fun x -> [x;x]);;
- : '_weak4 -> '_weak4 list = <fun>

但并不总是如此。当返回值类型不可变时，OCaml 通常可以推断出完全多态类型：

# identity [];;
- : 'a list = []

另一方面，如果返回类型可变，那么结果会是弱多态的：

# [||];;
- : 'a array = [||]
# identity [||];;
- : '_weak5 array = [||]

定义抽象数据类型时，会出现一个更重要的例子。考虑下面这个简单数据结构，它用于支持常量时间拼接的不可变列表类型：

# module Concat_list : sig
    type 'a t
    val empty : 'a t
    val singleton : 'a -> 'a t
    val concat  : 'a t -> 'a t -> 'a t  (* constant time *)
    val to_list : 'a t -> 'a list       (* linear time   *)
  end = struct

    type 'a t = Empty | Singleton of 'a | Concat of 'a t * 'a t

    let empty = Empty
    let singleton x = Singleton x
    let concat x y = Concat (x,y)

    let rec to_list_with_tail t tail =
      match t with
      | Empty -> tail
      | Singleton x -> x :: tail
      | Concat (x,y) -> to_list_with_tail x (to_list_with_tail y tail)

    let to_list t =
      to_list_with_tail t []

  end;;
module Concat_list :
  sig
    type 'a t
    val empty : 'a t
    val singleton : 'a -> 'a t
    val concat : 'a t -> 'a t -> 'a t
    val to_list : 'a t -> 'a list
  end

实现细节并不太重要，但需要注意，Concat_list.t 毫无疑问是不可变值。不过，在涉及值限制时，OCaml 会把它当作可变的：

# Concat_list.empty;;
- : 'a Concat_list.t = <abstr>
# identity Concat_list.empty;;
- : '_weak6 Concat_list.t = <abstr>

这里的问题是，签名由于是抽象的，遮蔽了 Concat_list.t 实际上是不可变数据类型这一事实。可以用两种方式之一解决这个问题：要么让类型具体化（也就是在 mli 中暴露实现），但这通常并不理想；要么把相关类型变量标记为协变（covariant）。第 13 章“对象（Objects）”会更详细学习协变和逆变；现在可以先把它理解为一种可以放在纯数据结构接口中的注解。

具体来说，如果把接口中的 type 'a t 替换为 type +'a t，就会在接口中明确表示该数据结构不包含对 'a 类型值的任何持久引用。这样一来，OCaml 就能为这种类型的非简单值表达式推断多态类型：

# module Concat_list : sig
    type +'a t
    val empty : 'a t
    val singleton : 'a -> 'a t
    val concat  : 'a t -> 'a t -> 'a t  (* constant time *)
    val to_list : 'a t -> 'a list       (* linear time   *)
  end = struct

    type 'a t = Empty | Singleton of 'a | Concat of 'a t * 'a t

    let empty = Empty
    let singleton x = Singleton x
    let concat x y = Concat (x,y)

    let rec to_list_with_tail t tail =
      match t with
      | Empty -> tail
      | Singleton x -> x :: tail
      | Concat (x,y) -> to_list_with_tail x (to_list_with_tail y tail)

    let to_list t =
      to_list_with_tail t []

  end;;
module Concat_list :
  sig
    type +'a t
    val empty : 'a t
    val singleton : 'a -> 'a t
    val concat : 'a t -> 'a t -> 'a t
    val to_list : 'a t -> 'a list
  end

现在，可以把恒等函数应用到 Concat_list.empty，而不会丢失多态性：

# identity Concat_list.empty;;
- : 'a Concat_list.t = <abstr>

9.9 小结（Summary）

本章覆盖了相当多内容，包括：

• 讨论可变数据结构的构建块，以及 for 循环、while 循环和顺序运算符 ; 等基本命令式构造

• 逐步实现几个经典命令式数据结构

• 讨论记忆化和惰性这类所谓良性副作用

• 覆盖 OCaml 用于阻塞 I/O 的 API

• 讨论求值顺序、弱多态等语言层面问题如何与 OCaml 的命令式特性交互

这里材料的范围和复杂度，显示了 OCaml 命令式特性的重要性。OCaml 默认不可变这一事实，不应该掩盖命令式编程是构建任何严肃应用的基本组成部分这一事实；如果你想成为有效的 OCaml 程序员，就需要理解 OCaml 对命令式编程的处理方式。