第八章 命令式编程

到目前为止，本书所示的大部分代码，实际上，应该是一般的OCaml代码，都是纯函数式的。纯函数式代码不会修改程序内部状态，没有I/O操作，不去读时钟，也不会以其它方式与外部的可变部分交互。因此一个纯函数行为类似一个数学方程式，对给定的输入总是会返回相同的结果，除了返回值之外对外部没有任何影响。另一方面，命令式代码通过副作用运作，修改程序内部状态或与外部交互。命令式函数有新的作用，并潜在每次调用返回不同的值的可能。

OCaml中默认的是函数式代码，原因是容易推导、错误更少且可组合性更好。但对于实用的编程语言来说，命令式代码有根本的重要性，因为现实世界的任务要求你与外部交互，这是其本性。命令式编程在性能方面也很重要。尽管OCaml中的纯函数代码很高效，但有许多算法只能用命令式技术高效实现。

在这方面OCaml提供了今人满意的折衷，使纯函数式编程容易且自然的同时，也对命令式编程提供了良好的支持。本章会带你领略OCaml的命令式特性，帮助你更好地使用他们。

例子：命令式字典

我们以一个简单的命令式字典开始，即，一个键和值都可变的映射。这仅仅是用于展示，Core和标准库都提供了命令式字典，在现实的任务中，你应该使用那些实现。第13章有更多使用Core实现的建议。

我们现在描述的字典，和Core及标准库中的一样，将使用哈希表实现。我们将使用开放哈希，一个哈希表是一个存储单元(bucket)的数组，每个存储单元包含一个键/值序对的列表。

下面是以mli文件形式提供的接口。类型('a, 'b) t表示一个键类型为'a，值类型为'b的字典：

(* file: dictionary.mli *)
open Core.Std

type ('a, 'b) t

val create : unit -> ('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文件中还包含一组辅助函数，其目的和行为可以从名字和类型签名中猜个八九不离十。注意有多个函数，像添加和修改字典的函数，都返回unit。这些是典型地通过副作用发挥作用的函数。

现在我们一块块地过一下实现（包含在ml文件中），解释遇到各种命令式构造。

第一步是把字典类型定义成一个有两个字段的记录：

(* file: dictionary.ml *)
open Core.Std

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

第一个字段length被声明成可变的。在OCaml中，记录默认是不可变的，但是单独的字段可以标记成可变的。第二个字段buckets是不可变的，但是包含了一个数组，这个数组本身就是个可变数据结构。

现在我们开始组建操作字典的基本函数：

let num_buckets = 17

let hash_bucket key = (Hashtbl.hash key) mod num_buckets

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

let length t = t.length

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

注意num_buckets是个常数，意味着我们桶数组是定长的。一个实际的实现需要随着字典元素的增加而增长这个数组，但此处为了简化我们忽略这一点。

hash_bucket函数在模块的其余部分都要使用，用以选择一个给定的键在数组中的存储位置。基于Hashtbl.hash实现，这是一个OCaml运行时提供的函数，可以用在任何类型上。因此其自身的类型是多态的：'a -> int。

上面定义的其它函数就相当明了了：

• create
  创建一个空字典。
• length
  从相应的记录字段中提取长度，返回保存在字典中的元素数。
• find
  在表中查找一个键，如果找到就以option类型返回相关的值。

find中展示了另一个重要的命令式语法：我们用array.(index)来提取数组的值。find也用到了List.find_map，你可以在toplevel中查看其类型:

# 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会对字典中的每个键/值对调用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',_) -> key' = key)

let add t ~key ~data =
  let i = hash_bucket 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',_) -> 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 key in
  if bucket_has_key t i key then (
    let filtered_bucket =
      List.filter t.buckets.(i) ~f:(fun (key',_) -> key' <> key)
    in
    t.buckets.(i) <- filtered_bucket;
    t.length <- t.length - 1
  )

上面的代码更复杂一些，因为我们需要检查是不是在重写或删除已存在的绑定，以确定是否需要修改t.length。辅助函数bucket_has_key即用于此。

add和remove都展示了一个语法：使用<-操作符更新数组元素（arrray.(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。

注意我们把所有副作用操作都放到每个函数的末尾执行。这是一个好的实践，因为这样最小化了这些操作被异常打断从而使数据结构状态不一致的机会。

原生的可变数据

现在我们已经看过了一个完整例子，让我们更系统地看一个OCaml中的命令式编程。上面我们碰到了两种不同形式的可变数据：有可变字段的记录和数组。我们现在和其它OCaml中其它原生可变数据一起更深入讨论一下。

类数组数据

OCaml支持好几种类数组数据结构，也就是以整数为索引的容器，提供了常数时间的元素访问操作。本节我们讨论其中几种：

普通数组

array类型用以通用目的的多态数组。Array模块有大量和数组交互的工具函数，包括一些修改操作。这其中包括Array.set，用以设置一个单独元素，以及Array.blit，用以高效地在两个索引范围间拷贝数据。

Array也有特殊的语法用以从一个数组中提取元素：

<array_expr>.(<index_expr>)

也可以设置数组中的一个元素：

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

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

数组字面写法使用[|和|]作为分隔符。因此，[| 1; 2; 3 |]是一个字面整数数组。

字符串

字符串本质上是字节数组，通常用在文本数据上。使用string而不是Char.t array（一个Char.t是一个8比特字符）的主要优势在于空间效率上；数组使用一个字--在64位系统上有8字节--来存储一个元素，而字符串每个字符只要一个字节。

字符串也有其自己的存取语法：

<string_expr>.[<index_expr>]
<string_expr>.[<index_expr>] <- <char_expr>

字符串字面值是用双引号包围的。同样也存在一个String模块，里面你可以找到字符串相关的有用函数。

Bigarrays

Bigarray.t是一个OCaml堆之外的内存块句柄。主要用以和C或Fortran交互，第20章会讨论。Bigarray也有自己的存取语法：

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

可变记录和对象字段以及引用单元(Ref Cells)

如我们所见，记录类型默认是不可变的，但是单独的记录字段却可以声明为可变的。这些可变字段可以用<-设置，即，record.field <- expr。

在11章我们会看到，一个对象的字段也可以类似地声明成可变的，也可以用与修改记录字段相同的方法进行修改。

引用单元

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 = {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>

外部函数

OCaml中另一部分命令式操作来自通过OCaml的外部函数接口（FFI）与外部库的交互。FFI使OCaml可以处理由系统调用或其它外部库导出的命令式结构。其中许多都是内建的，如访问write系统调用或访问时钟，而其它的则是来自用户库，像LAPACK绑定。OCaml的FFI会在第19章详细讨论。

for和while循环

OCaml支持传统的命令式循环结构，即for和while循环。它们都不是必须的，因为可以用递归函数模拟。然而，显式的for和while循环更简洁且在命令式编程中也更常用。

两者中for循环要简单些。实际上，我们已经用过for了--Dictionary中的iter函数中就是使用它创建的。这里有一个for的简单例子：

# 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循环，它包含一个条件和一个主体。循环先求值条件，然后，如果求值结果为真，就求值主体并再次启动循环。下面是一个简单例子，就地反转一个数组：

# 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 *)
      incr i;
      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|]

上例中，我们使用了incr和decr，它们是内建的函数，分别将一个int ref加一或减一。

例子：双向链表

另一个常见的命令式数据结构是双向链表。双向链表可以从两个方向遍历，元素的添加和删除是常数时间。Core定义了一个双向列表（模式名Doubly_linked），但我们为了演示还是要定义自己的双向链表。

这是模块的mli文件:

(* file: dlist.mli *)
open Core.Std

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开始：

(* file: dlist.ml *)
open Core.Std

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

type 'a t = 'a element option ref

'a element是一个记录，包含一个该节点存储的值，还有指向前一个和后一个元素的option（同时也是可变的）字段。在列表头，前导元素是None，在列表尾，后续元素是None。

列表自身的类型是一个option元素的可变引用。列表为空时这个引用是None，否则是Some。

现在我们可以定义操作列表和元素的基本函数了：

let create () = ref None
let is_empty t = !t = None

let value elt = elt.value

let first t = !t
let next elt = elt.next
let prev elt = elt.prev

我些都是从我们的类型定义中直接得出的。

循环数据结构

双向链表是循环数据结构，就是说可能沿着一个非平凡的指针序列可以接近自身。通常构建循环数据结构都要求副作用。先构建数据元素，然后使用向后赋值添加循环。

但有一个例外：你可以使用let rec构建固定长度的循环数据结构：

# let rec endless_loop = 1 :: 2 :: 3 :: endless_loop;;
val endless_loop : int list =
  [1; 2; 3; 1; 2; 3; 1; 2; 3;
   1; 2; 3; 1; 2; 3; 1; 2; 3;
   1; 2; 3; 1; 2; 3; 1; 2; 3;
   ...]

然而这种方法作用很有限。通用目的的循环数据结构需要能修改。

修改列表

现在我们开始考虑修改列表的操作，从insert_first开始，它用以在列表头部插入一个元素：

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

insert_first首先定义了一个新元素new_elt，然后将其连到列表上，最后把列表本身指向new_elt。注意match语句的优先级是非常低的，为了和后面的赋值语句（t := Some new_elt）分开，我们使用begin ... end将其包围。我们也可以使用小括号达到同样的目的。如果没有某种形式的括号，最后的赋值会错误地成为None分支的一部分。

我们可以使用insert_after在列表的元素后插入元素。insert_after以一个要在其后插入新节点的元素和一个要插入的值为参数：

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

最后我们需要一个remove函数：

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

上面的代码在前后元素存在时，小心地修改了后面元素的prev指针和前面元素的next指针。如果没有前导元素，要更新列表自身的指针。任何情况下，都要把被删除元素前导和后续元素指针设置为None。

上面的函数比看起来要脆弱得多。错误使用接口可能导致毁坏的数据。如，重复删除一个元素会导致列表的主引用被置为None，这会清空列表。删除一个列表中不存在的列表也会导致类似的问题。

也并不意外。复杂的数据结构肯定更难处理，比其纯函数式的替代需要更多技巧。前面说的问题可以通过更小心的错误检查来处理，且这样的错误在Core的Doubly_linked模块中都得到了小心处理。你应该尽可能地使用设计良好的库中的命令式数据结构。如果不行，你应该确保在错误处理上加倍小心。

迭代函数

当定义列表、字典和树这样的容器时，你通常需要定义一组迭代函数，如iter、map和fold，使用它们来简洁地表达通用迭代模式。

Dlist有两个这种迭代器：iter，目标是按顺序在列表的每一个元素上调用一个产生unit的函数；还有find_el，在列表的每一个元素这运行一个测试函数，返回第一个通过测试的元素。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_link这样的模块，它们更完整，也处理了更多棘手问题。尽管如此，本例还是展示了OCaml中你可以用来构建重要命令式数据结构的技术，同时还有陷阱。

惰性和温和影响

Laziness and Benign Effects

很多时候，你都想基本上用纯函数式风格编程，只有限地使用副作用来提高代码效率。这种副作用有时称为 温和影响，这是一种既能使用命令式特性又能保留纯函数式好处的很有用的方法。

最简单的温和影响就是 惰性。一个惰性值就是一个不真正使用不计算的值。在OCaml中，惰性值使用lazy关键字创建，它可以把一个类型为s的表达式转换成类型为s Lazy.t的惰性值。表达式的求值被推迟，直到强制调用Lazy.force：

# let v = lazy (print_string "performing lazy computation\n"; 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

lazy_state表示一个惰性值的可能状态。运行之前惰性值是Delayed，Delayed持有一个用于计算的函数。计算被强制执行完成并正常结束后惰性值是Value。当计算被强制执行，但抛出了异常时使用Exn实例。一个惰性值就是一个简单的lazy_state引用。ref使得可以从Delayed状态转换到Value或Exn。

我们可以从一个代码块创建一个惰性值，即，一个接收一个unit参数的函数。把表达式包装在一个代码块中是另一种暂停计算表达式的方式：

# let create_lazy f = ref (Delayed f);;
val create_lazy : (unit -> 'a) -> 'a lazy_state ref = <fun>
# let v = create_lazy
(fun () -> print_string "performing lazy computation\n"; sqrt 16.);;
val v : float lazy_state ref = {contents = Delayed <fun>}

现在我们只要一个强制执行惰性值的方法。下面代码即可做到：

# let force v =
    match !v with
    | Value x -> x
    | Exn e -> raise e
    | Delayed f ->
    try
      let x = f () in
      v := Value x;
      x
    with exn ->
      v := Exn exn;
      raise exn
;;
val force : 'a lazy_state ref -> 'a = <fun>

我们可以使用Lazy.force一样来使用它：

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

我们实现的和内建惰性之间用户能看到的不同就是语法。相对于create_lazy (fun () -> sqrt 16.)，我们（使用内建的lazy）只写lazy (sqrt 16.)就可以了。

记忆和动态编程

Memoization and Other Dynamic Programming

另一个温和影响是 记忆。一个记忆函数可以记住之前调用的结果，因此之前调用的参数再次出现时，就可以直接返回而不用继续计算。

这里有一个函数接收任意一个单参数函数为参数，返回其记忆版本。这里我们使用了Core的Hashtbl模块，而没有使用我们自己的玩具Dictionary：

# let memoize f =
    let table = Hashtbl.Poly.create () in
    (fun x ->
      match Hashtbl.find table x with
      | Some y -> y
      | None ->
        let y = f x in
        Hashtbl.add_exn table ~key:x ~data:y;
        y
    );;
val memoize : ('a -> 'b) -> 'a -> 'b = <fun>

上面的代码有点技巧。memoize接收一个函数f作为参数，然后分配一个哈希表（叫table）并返回一个新的函数作为f的记忆版本。当新函数被调用时，先查表，查找失败才会调用f并把结果存到table中。只要memoize返回的函数在作用域内，table就有效。

当函数重新计算很昂贵且你不介意无限缓存旧结果时，记忆非常有用。重要警告：记忆函数天生就是内存泄漏。只要你使用记忆函数，你就持有了其到目前为止的每一个返回结果。

记忆也用于高效实现一些递归算法。计算两个字符串的编辑距离（也称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 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" "ocaml"
edit_distance "OCaml" "ocam"
edit_distance "OCam" "ocam"

这样又会按顺序分配其它的调用：

edit_distance "OCam" "ocaml"
   edit_distance "OCa" "ocaml"
   edit_distance "OCam" "ocam"
   edit_distance "OCa" "ocam"
edit_distance "OCaml" "ocam"
   edit_distance "OCam" "ocam"
   edit_distance "OCaml" "oca"
   edit_distance "OCam" "oca"
edit_distance "OCam" "ocam"
   edit_distance "OCa" "ocam"
   edit_distance "OCam" "oca"
   edit_distance "OCa" "oca"

如你所见，这些调用中有一些是重复的。如有两个不同的edit_distance "OCam" "oca"调用。随着字符串大小的增长冗余数以指数级增加，这意味着我们的edit_distance在处理大字符串时非常非常慢。我们可以通过写一个简单计时函数来看一下：

# let time f =
    let start = Time.now () in
    let x = f () in
    let stop = Time.now () in
    printf "Time: %s\n" (Time.Span.to_string (Time.diff stop start));
    x ;;
val time : (unit -> 'a) -> 'a = <fun>

我们现在可以用这个函数来试验一些例子：

# time (fun () -> edit_distance "OCaml" "ocaml");;
Time: 1.40405ms
- : int = 2
# time (fun () -> edit_distance "OCaml 4.01" "ocaml 4.01");;
Time: 6.79065s
- : int = 2

几个额外字符就能导致慢几千倍。

这里记忆就可以帮上大忙了，但要修复这个问题，我们要记住edit_distance对其自己的调用。这种技术有时被称作动态编程。为了弄明白如何做，我们把edit_distance放一边，先考虑一个简单得多的例子：计算斐波纳契数列的第n个元素。斐波纳契数列定义为，以两个1开始，后续元素是前面两个的和。经典的递归计算如下：

# let rec fib i =
    if i <= 1 then 1 else fib (i - 2) + fib (i - 1);;

但是这个实现指数级地慢，和edit_distance慢的原因相同：我们对fib做了很多重复调用。性能方面相当有明显：

# time (fun () -> fib 20);;
Time: 0.844955ms
- : int = 10946
# time (fun () -> fib 40);;
Time: 12.7751s
- : int = 165580141

如你所见，fib 40比fib 20慢了几千倍。

那么，我们如何使用记忆来加速呢？技巧就是我们需要在fib中的递归调用前插入记忆。我们不能以普通方式定义fib然后再记忆它以期待fib的第一个调用被提升：

# let fib = memoize fib;;
val fib : int -> int = <fun>
# time (fun () -> fib 40);;
Time: 12.774s
- : int = 165580141
# time (fun () -> fib 40);;
Time: 0.00309944ms
- : int = 165580141

为了加速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>

现在我们可以连接递归节点(recursive knot)来把它转成一个普通的斐波纳契函数：

# 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喂给它自己，从面形成了一个真正的递归函数。

这种做法挺聪明的，但我们真正要做的是要找到一种方法来实现之前的很慢的斐波纳契函数。要使它更快，我们需要一个make_rec的变体，可以在绑定递归节点时插入记忆。我们称之为memo_rec：

# let memo_rec f_norec x =
    let fref = ref (fun _ -> assert false) in (* 下面这几句是创建递归的一种方法，此函数是占位用的。 zhaock *)
    let f = memoize (fun x -> f_norec !fref x) in
    fref := f;
    f x
  ;;
val memo_rec : (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b = <fun

注意memo_rec和make_rec签名相同。

这里我们用引用来连接递归节点，而不是let rec，原因我们稍后讨论。

使用memo_rec，现在我们可以构建fib的高效版本了：

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

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

记忆行为在这里很重要。如果回头看一下memo_rec的定义，你会看到调用memo_rec lib_norec没有触发memoize调用。只有fib被调用从而memo_rec最终的参数确定时，memoize才会被调用。调用结果在fib返回时就超出作用域了，所以调用memo_rec不会有内存泄漏--记忆表在计算结束时被回收了。

我们可以把memo_rec作用一个单独声明的一部分，这让它看起来更像是let rec的一种特殊形式：

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

用记忆来实现斐波纳契有点小题大作了，实际上，上面的fib也不是特别高效，需要按传给fib的数线性分配空间。写一个只用常数空间的斐波纳契函数是很容易的。

但是对于edit_distance，记忆却是一个好方法，我们可以使用和fib一样的方法。我们需要修改一下edit_distance使它把一对字符串接收为一个参数，因为memo_rec只能作用于单参数函数上。（我们总是可以使用封装函数来覆盖原始接口。）这样的修改加上memo_rec的调用，我们就得到了一个有记忆版的edit_distance:

# let edit_distance = memo_rec (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 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比之前的要高效得多；下面的调用比没有记忆的版本快了几千倍：

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

let rec的局限性

你可能想知道，在memo_rec中连接递归节点时为什么不像先前make_rec中那样使用let rec。代码如下：

# let memo_rec f_norec =
    let rec f = memoize (fun x -> f_norec f x) in
    f
 ;;
Characters 39-69:
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右边只允许三种结构：一个函数定义，一个构造函数，或一个惰性值。这排除了一些合理的东西，如我们的memo_rec定义，但它同样也挡住了不合理的东西，像我们对x的定义。

值得一提的是在一种像Haskell这样的惰性语言中不会有这个问题。实际上，我们可以使用OCaml的惰性特性使类似上面x的定义可行：

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

当前，真的试图计算会失败。Ocaml的lazy在一个惰性值试图把强制求值自己作用计算的一部分时会抛异常.

# Lazy.force x;;
Exception: Lazy.Undefined.

但我们还是可以用lazy创建有用的递归定义。实际上，我们可以用惰性来定义我们的memo_rec，而不是显式修改：

# let lazy_memo_rec f_norec x =
    let rec f = lazy (memoize (fun x -> f_norec (Lazy.force f) x)) in
    (Lazy.force f) x
  ;;
val lazy_memo_rec : (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b = <fun>
# time (fun () -> lazy_memo_rec fib_norec 40);;
Time: 0.0650883ms
- : int = 102334155

惰性比显式修改有更多的约束，所以有时会使代码更易懂。

输入输出

命令式编程可不只修改内存数据这么些。任何参数和返回值没有确实转换关系的函数本质都是命令式的。这不仅包括修改你的程序数据，还有和程序外部世界交互的操作。其中一个重要例子就是I/O，即从文件、终端输入输出和网络套接字读写数据的操作。

OCaml中有好几个I/O库。本节我们要讨论OCaml带缓存的I/O库，可以通过Core的In_channel和Out_channel模块使用。其它I/O原语可以通过Core的Unix模块和Async获得，异步I/O库在18章介绍。Core的In_channel和Out_channel模块（包括Unix模块）的多数功能都源于标准库，但此处我们会使用Core的接口。

终端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非常有用，以至于它们可以在全局作用域中直接使用，不需要通过In_channel和Out_channel模块。

让我们看一下它们在一个简单命令式程序中的应用。下面的程序，time_converter，提示用户输入一个时区，然后打印那个时区的当前时间。这里，我们使用了Core的Zone模块地查询时区，用Time模块来计算当前时间并以相应的时区打印出来：

(* 本例中Zone似乎要使用Core.Zone *)
open Core.Std

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 = 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 ";Zone.to_string zone;" is ";time_string;".\n"]);
    Out_channel.flush stdout

我们可以使用corebuild构建程序并运行之。你会看到它提示你输入，如下所示：

$ corebuild time_converter.byte
$ ./time_converter.byte
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不会每次调用outpt_string后立即执行一个写操作。而是将写操作缓存，直到写了足够多从而触发了缓存刷新，或是显式请求了一个刷新操作。通过减少系统调用次数极大增加了写处理的效率。

注意In_channel.input_line返回一个字符串option，None表示输入流结束（即，一个文件结束条件）。Out_channel.output_string用以打印最后的输出，并调用Out_channel.flush把输出刷新到屏幕上。最后的那个刷新技术上说是不需要的，因为程序接着就结束了，此时所有剩余的输出都会被刷新，但显式的刷新仍不失为一个好实践。

使用printf格式化输出

像Out_channel.output_string这样的生成输出的函数很简单且容易理解，但是有点冗长。OCaml也支持使用printf函数格式化输出，它仿照了C语言标准库中的printf。printf接收一个描述打印内容和格式的格式化字符串，还有要打印的参数，由格式化字符串中的格式化指令确定。然后，我们就可以写出以下例子：

# 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;;
Characters 26-29:
Error: This expression has type float but an expression was expected of type
int

理解格式化字符串

printf中使用的格式化字符串和普通的字符串有很大的不同。这种不同是因为OCaml中的格式化字符串，不像C语言中的，是类型安全的。编译器会检查格式化字符中引用的类型和printf其余参数类型的匹配。

为了检查这一点，OCaml需要在编译期分析格式化字符串的内容，这意味着格式化字符串需要在编译期就是一个可获得的字符串常量。实际上，如果你试图传递一个普通字符串给printf，编译器会报错：

# let fmt = "%i is an integer, %F is a float, \"%s\" is a string\n";;
val fmt : string = "%i is an integer, %F is a float, \"%s\" is a string\n"
# printf fmt 3 4.5 "five";;
Characters 9-12:
Error: This expression has type string but an expression was expected of type
         ('a -> 'b -> 'c -> 'd, out_channel, unit) format =
           ('a -> 'b -> 'c -> 'd, out_channel, unit, unit, unit, unit)
           format6

如果OCaml推导出一个给定的字符串是一个格式化字符串，它就会在编译期解析它，根据找到的格式化指令选择其类型。因此，如果我们添加一个类型注释表明我们定义的字符串实际上是一个格式化字符串，它就会被像下面这样解释：

# let fmt : ('a, 'b, 'c) format =
    "%i is an integer, %F is a float, \"%s\" is a string\n";;
val fmt : (int -> float -> string -> 'c, 'b, 'c) format = <abstr>

于是我们可以把它传给printf：

# printf fmt 3 4.5 "five";;
3 is an integer, 4.5 is a float, "five" is a string
- : unit = ()

如果这看起来和你之前看到的不一同样，那是因为它确实不一样。这确实是类型系统的特例。大多数时候，你不需要关心这种对格式化字符串的特殊处理--你可以使用printf而无需关心细节。但脑子里对这一点有一个大体印象还是有用的。

现在看看可以如何使用printf重写时间转换程序，使它更简洁一点：

open Core.Std

let () =
  printf "Pick a timezone: %!";
  match In_channel.input_line stdin with
  | None -> failwith "No timezone provided"
  | Some zone_string ->
    let zone = 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%!" (Zone.to_string zone) time_string

上例中，我们只使用两个格式化指令：%s，用以包含一个字符串，和%!，使printf刷新通道。

printf的格式化指令提供了很多控制，让你可以指定下面的内容：

• 对齐和填充
• 字符串转义规则
• 数字应该格式化为十进制、十六进制还是二进制
• 浮点转换精度

还有一些类printf的函数，输出目标不是stdout，包括：

• eprintf，打印到stderr
• fprintf，打印到任意通道
• sprintf，返回一个格式化的字符串

这些，还有更多的内容，在OCaml手册的Printf模块API文档中都有描述。

文件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 -> 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\"").

如果我们在一个循环里一遍一遍这样做，最终会耗尽文件描述符：

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

现在，要打开更多文件你就必须要重启toplevel。

要避免这种情况，你就要保证你的代码在调用后会完成清理工作。我们可以用第七章中描述的protect函数来做到这一点，如下所示：

# let sum_file filename =
    let file = In_channel.create filename in
    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") 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.withfile filename ~f:(fun file ->
      let numbers = List.map ~f:Int.of_string (In_channel.input_lines file) in
      List.fold ~init:0 ~f:(+) numbers)
  ;;

我们的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文档。

求值顺序

表达式求值顺序是定义一门编程语言的重要部分，在命令式编程中尤为重要。你碰到的大多数编程语言都是 严格的，OCaml也是。在一门严格的语言中，当你把一个标识符绑定到一些表达式的结果时，表达求值要先于变量绑定。类似的，如果你在一组参数上调用函数，那些参数都在传给函数前求值。

考虑下面这个简单例子。我们有一组角度，想要确定它们中是否有负的sin值。下面的代码片可以回答这个问题：

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

在某种意义上，我们不需要求值sin 128.。因为sin 75.是负的，所以我们在计算sin 128.之前就已经知道答案了。

但不必非要如此。使用lazy关键字，我们可以重写原始计算，这样sin 128.就不会计算了：

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

我们可以放置一些打印来确认这一点：

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

OCaml默认是严格的原因很合理：惰性求值和命令式编程通常不好混用，因为惰性使推导一个副作用何时发生变得更困难。理解副作用调用顺序对推导一个命令式程序至关重要。

在一门严格的语言中，我们知道一系列用let绑定的表达式会按定义的顺序求值。但同一个表达式中的求值顺序呢？官方的说法是，表达式内部的求值顺序是未定义的。实际上，OCaml只有一个编译器，其行为即是事实标准。但不幸的是，求值顺序经常和预期相反。

看下面的例子：

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

这里，你会看到最后出现的子表达式实际上是最先计算的。许多类型的表达式都是这样的。如果你要明确子表达式的求值顺序，只能用一系列let绑定表达它们。

副作用和弱多态

看一下下面这个简单的命令式程序：

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

remeber只是简单地缓存了传给它的第一个值，每次调用都返回这个值。因为cache在remember调用之间只被创建和初始化一次。

remember不是一个很有用的函数，但它抛出了一个有趣的问题：其类型是什么呢？

第一次调用时，remember返回传给它的值，这意味着其输入输出类型要匹配。相应的，对类型t，remember的类型应该是t -> t。remeber对t的选择不必非要绑定到特定类型上，所以你可能期待OCaml会将其一般化，用一个多态类型代替t。就是这种泛化，给了我们多态类型。举个例子，identity函数，就是这样获得多态类型的：

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

如你所见，identity的多态类型使其可以操作不同类型的值。

但这不适用于remember。在上例中你已经看到了，OCaml推导出的remember类型看起来和identity很像，但又不完全一样。再看一下：

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

类型变量'_a中的下划线告诉我们这个变量仅仅是 弱多态的，就是说它可以被用在任何 单独类型上。这是合理的，因为，不像identity，remember总是返回第一次调用时传给它的值，这意味着其返回值都是相同类型的。

OCaml一旦知道了要使用的具体类型，就会把弱多态转换成一个具体类型：

# let remember_three () = remember 3;;
val remember_three : unit -> int = <fun>
# remember;;
- : int -> int = <fun>
# remember "avocado";;
Characters 9-18:
Error: This expression has type string but an expression was expected of type
int

注意remember的类型由remember_three确定，尽管它从未被调用。

值约束

那么，编译器何时会推导出弱多态类型呢？正如你看到的，当一个类型未知的值保存在一个永久可变单元中时，我们需要弱多态类型。因为类型系统没有精确到可以确定所有可能情况，OCaml使用了一种简单的规则来标记不引入任何永久可变单元的情况，只在那些情况下推导出多态类型。这条规则叫作 值约束.

值约束的核心是一些类型的表达式，我们称之为 简单值，本质上就不能引入可变单元：

• 常量（即，整数和浮点数字面值一类的东西）
• 只包含简单值的构造函数
• 函数声明，即，以fun或function开头的表达式，或其等价的let绑定，let f x = ...
• 形如let var = expr1 in expr2的let绑定，其中expr1和expr2都是简单值

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

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

但如果我们写一个按上面的定义不是简单值的表达式，就会得到不同的结果。举个例子，考虑如果我们要记忆前面的定义的函数：

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

函数的记忆版本实际上需要被限制到一个类型上，因为它后台使用可变状态来缓存该函数前面调用的结果。但即使是这个函数没有做这一点，OCaml还是会得出同样的结论。看下面的例子：

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

这里推导出一个完全多态的变量是安全的，但因为OCaml的类型系统不区分纯的和不纯的函数，它无法区分这两种情况。

值约束不要求没有可变状态，只是要没有 永久的的可变状态在同一个函数的调用之间共享数据。因此，一个每次调用都会产生新的引用的函数也可能是完全多态的：

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

但用有跨多次调用的永久可变缓存的函数，像momoize，就只能是弱多态的。

偏特化应用和值约束

大多数时候，值约束起作用时都是合理的，即，因为这个值实际上只能安全地用在单独一个类型上。但有时，值约束不是你想要的。这些情况中最常见的就是偏特化应用函数。一个偏特化应用函数，像函数应用一样都不是简单值，所以，用偏特化创建的函数有时没有你想像的那么通用。

看一下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 -> '_a) -> '_a 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 expansion，常用于解决值约束引发的问题。

放松值约束

OCaml对多态类型的推导实际上比上面说的要好一些。值约束基本上是一个语法检查：你可以做一些简单值的操作，任何是简单值的东西都可以泛化。

但OCaml实际上有一个宽松版的值约束，可以利用类型信息来允许不是简单值的多态类型。

例如，我们看到一个函数调用，即使是像identity这么简单的，也不是一个简单值，会把一个多态值变成一个弱多态值：

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

但并不总是这样。当返回值是不可变的时，OCaml就会推导出一个完全多态类型：

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

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

# [||];;
- : 'a array = [||]
# identity [||];;
- : '_a 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.t是一个明确的不可变值。但遇到值约束时，OCaml会将其看成可能变化的：

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

问题在于其签名，抽象性掩盖了Concat_list.t是不可变数据这个事实。我们可以使用下面两种中的任一种方法来解决此问题：或使类型具体化（即在mli文件中暴露实现），这通常不令人满意；或把类型变量标记成 协变量(covariant.)。关于协变量和抗变性我们会在第11章会学习更多，但现在，你可以把它理解成一个可以放在一个纯函数式数据结构接口中的标注。

实践中，如果你用+'a代替接口的'a，就是显式地表明接口的数据结构不会包含类型'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

    ...

  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函数而不必损失多态性了：

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

总结

本章内容很多，包括：

• 讨论了可变数据结构的构造块，也是基本的原生命令式结构，如for循环、while循环、和序列操作符;
• 过了一遍一些经典命令式数据结构的实现
• 讨论了被称了温和影响的记忆和惰性
• 涉及了OCaml的阻塞I/O API
• 讨论了一些语言层面的问题，如求值顺序和弱多态，是如何与OCaml的命令式特性相互作用的

材料的范围和复杂性反映了OCaml中命令式特性的重要程度。OCaml默认是不可变的这一点并不能掩盖命令式编程也是构建任何严肃程序的基础之一这个事实，如果你相成为一个高效的OCaml程序员，就需要理解OCaml的命令式编程方法。