Chap3 列表和模式

列表基础

列表构造，表示基础，[; ;]语法糖，::直接构造。空表[]用来结束一个列表。空表是多态的，这意味着它可以用于任意类型的元素。

let empty_list = [];;
let one_element_list = 3::empty_list;;
let one_element_list = "test"::empty_list;;

# let empty_list = [];;
val empty_list : 'a list = []
# let one_element_list = 3::empty_list;;
val one_element_list : int list = [3]
# let one_element_list = "test"::empty_list;;
val one_element_list : string list = ["test"]

使用模式从列表抽取数据

可以使用match语句从列表读出数据。注意match可以用来绑定变量，->左边，所以可能遮蔽原有定义。模式可以描述数据结构的布局，甚至可以包含直接量，一些练习：

let rec drop_value l to_drop =
  match l with
  | []-> []
  | to_drop::tl -> drop_value tl to_drop (* 绑定新的to_drop *)
  | hd::tl -> hd::drop_value tl to_drop;; (* 警告没有使用该match *)
drop_value [1;2;3;4;5;] 5;;     (* 由于非空都走了to_drop::tl 全删除了 *)

# let rec drop_value l to_drop =
  match l with
  | []-> []
  | to_drop::tl -> drop_value tl to_drop
  | hd::tl -> hd::drop_value tl to_drop;;
        Characters 103-109:
    | hd::tl -> hd::drop_value tl to_drop;;
      ^^^^^^
Warning 11: this match case is unused.
val drop_value : 'a list -> 'a -> 'a list = <fun>
# drop_value [1;2;3;4;5;] 5;;
- : int list = []

使用常规语句

let rec drop_value l to_drop =
  match l with
  | [] -> []
  | hd::tl ->
     let new_tl = drop_value tl to_drop in (* 使用常规的if而不是模式匹配来判断 *)
     if hd = to_drop
     then new_tl
     else hd::new_tl
;;
drop_value [1;2;3;4;5;] 5;;

#
let rec drop_value l to_drop =
  match l with
  | [] -> []
  | hd::tl ->
     let new_tl = drop_value tl to_drop in (* 使用常规的if而不是模式匹配来判断 *)
     if hd = to_drop
     then new_tl
     else hd::new_tl;;
              val drop_value : 'a list -> 'a -> 'a list = <fun>
#   drop_value [1;2;3;4;5;] 5;;
- : int list = [1; 2; 3; 4]

模式匹配的优劣，基于match的实现比基于if的实现快很多倍。之所以存在这个差别，是因为我们实际上需要把相同的工作做很多次。

• 性能：

  模式匹配要比手工编写的其他代码更为高效。不过，字符串的匹配有所例外，实际上这会顺序地进行测试，所以如果匹配包含一个很长的字符串序列，这些匹配可能还不如散列表。但大多数情况下，模式匹配在性能上都明显有优势。

• 检测错误：

  OCaml 能够查找模式匹配中的问题：在drop_value的错误实现中，OCaml 提醒我们最后一个情况是多余的。

  OCaml 还会检查match语句的完备性，编译器对于缺少的情况会产生警告，还会给出无法匹配的模式的一个例子。对于涉及用户自定义类型的例子，这种完备性检查的意义更重大。

  还相当于一种重构工具。可以指导你哪些地方需要调整代码来处理不断变化的类型。

有效使用 List 模块

• List.map 取一个列表和一个函数，对于列表每个元素使用map。
• List.map2_exn 取两个列表和一个函数，用函数结合两列表，_exn则是因为两个列表长度不一致，该函数会报错。
• List.fold 取一个要处理的列表，一个初始化的迭代器~init，以及用来更新这个累加器的函数。该函数遍历列表更新迭代器，返回最终迭代器的值。

List.fold ~init:[] ~f:(fun biao x -> x :: biao) [1;2;3;4];; (* List.fold 实验 *)

# List.fold ~init:[] ~f:(fun biao x -> x :: biao) [1;2;3;4];;
- : int list = [4; 3; 2; 1]

结合上述三个函数，计算列的最大宽度。

let max_width header rows =     (* 计算列的最大宽度 *)
  let lengths l = List.map ~f:String.length l in
  List.fold rows
    ~init:(lengths header)
    ~f:(fun acc row -> List.map2_exn  ~f:Int.max acc (lengths row));;

代码解释，利用List.map定义限制作用域的函数lengths,利用List.fold迭代每一行，迭代函数是利用List.map2_exn取最大值，初始化为标题行的长度。

后续代码示例中包括了根据获取长度利用String.make生成长度适当的短横线字符串。以及字符串连接，在字符串两边增加定界符。以及根据 padding 渲染每一行。

let render_separator widths =   (* width是数值列表，由上面maxwidth得到 *)
  let pieces = List.map widths
                 ~f:(fun w -> String.make (w+2) '-')
  in
  "|" ^ String.concat ~sep:"+" pieces ^ "|";;

let pad s length = (* 编写代码显示这些数据行 *)
  " " ^ s ^ String.make(length - String.length s + 1) ' ';;
pad "hello" 10;;

let render_row row widths =
  let padded = List.map2_exn row widths ~f:pad in
  "|" ^ String.concat ~sep:"|" padded ^ "|"
;;
render_row ["Hello";"World"] [10;15];;

关于 String.concat 和^的性能

由于^是一个成对处理字符串的操作符。要避免使用^来连接大量字符串，因为每次运行时，它都会分配一个新的字符串。组装大字符串时，^可能带来严重的性能问题。

最终汇集整个工作

let render_table header rows = (* 汇集整个工作建立表格 *)
  let widths = max_width header rows in (* 利用max_width获取梅列宽的widths *)
  String.concat ~sep:"\n"               (* 插入换行分隔符号 *)
    ( render_row header widths          (* 渲染header *)
      :: render_separator widths        (* 渲染分界 *)
    :: List.map rows ~f:(fun row -> render_row row widths) (* 为了渲染每一行，需要再次使用List.map *)
    );;

(* 测试一下最初的例子 *)
printf "\n%s\n"
  (render_table
      [ "language";"architect";"first class"]
      [ ["Lisp";"John McCarthy";"1958"];
        ["C";"Dennis Ritchie";"1969"];
        ["ML";"Robin Milner";"1973"];
        ["OCaml";"Xavier Leroy";"1996"];
      ]);;

| language | architect      | first class |
|----------+----------------+-------------|
| Lisp     | John McCarthy  | 1958        |
| C        | Dennis Ritchie | 1969        |
| ML       | Robin Milner   | 1973        |
| OCaml    | Xavier Leroy   | 1996        |
- : Base.unit = ()

其他有用的列表函数，参考在线文档（现在 page not found 了）

• List.reduce 特殊版本的fold，不需要一个明确的初始值 init。
• List.filter,List.filter_map 对列表中一个子集进行操作。
• List.append 进行列表的连接，合并,@运算符与函数等价。
• List.concat 用来连接一个由列表组成的列表。

尾递归

Tail Recursion，计算一个 OCaml 的长度，唯一的办法是从头到尾遍历整个列表。因此，计算列表长度花费的时间与列表的大小成正比。考虑下面两种写法，分别是简单函数和尾递归函数。

(* 非尾递归 *)
let rec length = function       (* 无名函数接受一个列表为参数 *)
  | [] -> 0
  | _ :: tl -> 1 + length tl
;;

(* 尾递归 *)
let rec length_plus_n l n =     (* 接受列表和数值两个参数 *)
  match l with
  | [] -> n
  | _ :: tl -> length_plus_n tl (n+1)
;;

let make_list n  = List.init n ~f:(fun x -> x);;
length_plus_n (make_list 500000) 0;;
length (make_list 500000);;

# length_plus_n (make_list 500000) 0;;
- : int = 500000
# length (make_list 500000);;
Stack overflow during evaluation (looping recursion?).
Raised by primitive operation at file "//toplevel//", line 51, characters 19-28

函数调用需要一些空间来跟踪与这个调用相关联的信息，如传入函数的参数，或者函数调用完成后开始执行的那个代码的位置。为了支持嵌套函数调用，常用一个堆栈来组织，对于各个嵌套的函数调用会分别分配一个新的栈帧，成功是再释放。非尾递归的函数会分配很多数量的栈帧，耗尽空间。而尾递归中的调用是一个尾调用可以巧妙避开这问题，不需要分配新的栈帧。

什么时候一个调用是尾调用？函数（调用者）调用另一个函数（被调用者）。被调用者的返回的值，如果调用者除了返回这个值不做任何其他处理，则认为这个调用是一个尾调用。尾调用优化很有意义，因为调用者完成一个尾调用时，调用者的栈帧不再使用，所以不用保留这个栈帧。因此，不用为被调用者分配一个新栈帧，编译器完全可以重用调用者的栈帧。

当嵌套调用序列深度与数据规模基本相同时，通常都应当使用尾递归。

更简洁更快速的模式

利用as模式减少分配，function可以替代显式的match，when子句可以让代码更为简介，为模式增加一个额外的前置条件。

练习

let rec destutter = function
  | [] | [_] as l -> l
  | hd::(hd :: _ as tl) when  hd =hd' -> destutter tl
  | hd:: tl -> hd :: destutter tl
;;

有关=的多态比较，类似的还有<,>=,compare，内置于运行时库的底层，基础是对于所比较的值的类型几乎完全忽略这些类型的有关信息，而只考虑值在内存中的结构。我们无法自行构建这些函数。另外注意一些使用限制，比如函数值的=比较会在运行时Fail。