Ocaml 入门

OCaml 是一种支持函数式、命令式和面向对象编程范式的静态类型语言。

函数式编程（Functional Programming）

函数式编程有以下几个特点：

immutable（不可变）
side effects（副作用）
referential transparency（引用透明）

Data is immutable：数据不可变

函数拿到一个参数后，不会把这个参数本身改掉，而是返回一个新值。

例子 1：把列表里的数都翻倍

函数式写法：

1	List.map (fun x -> x * 2) [1;2;3]

结果是：

[2;4;6]

这里原来的 [1;2;3] 没有被改掉，而是产生了一个新的列表 [2;4;6]。

可以理解成：

命令式：把旧东西改一改
函数式：保留旧东西，造一个新东西

对比例子：命令式修改数组

int[] arr = {1, 2, 3};
for (int i = 0; i < arr.length; i++) {
    arr[i] = arr[i] * 2;
}

执行后，arr 自己变成了 {2,4,6}。
也就是说，原数据被改了。

Pure functions have no side effects：纯函数没有副作用

副作用就是：函数除了“返回结果”，还偷偷影响了别的东西。

纯函数例子：

1	let square x = x * x

这个函数很“干净”：

输入 3 就返回 9
输入 5 就返回 25
它不会打印东西
不会改全局变量
不会修改参数

所以这是纯函数。

有副作用的例子：

int counter = 0;

int count() {
    counter = counter + 1;
    return counter;
}

这个函数每次调用都会修改外部变量 counter。

比如：

第一次 count() 返回 1
第二次 count() 返回 2
第三次 count() 返回 3

问题在于只看 count() 这行，根本不知道结果是多少，因为它取决于之前调用过几次。所有这个函数不纯。

Referential transparency：引用透明

如果一个表达式是“纯”的，那你可以直接用它的值替换它，程序结果不会变。

例子 1：纯函数可以直接替换

1 2	let square x = x * x square (2 + 3)

因为 2 + 3 = 5，所以这句等价于：

square 5

而 square 5 = 25，所以也等价于：

整个替换过程没问题：

1
2
3

square (2 + 3)
=> square 5
=> 25

这就是引用透明。

例子 2：有副作用时就不能随便替换

看这个：

int counter = 0;

int count() {
    counter++;
    return counter;
}

如果程序里有：

1	count() + count()

实际计算是：

第一次 count() -> 1
第二次 count() -> 2
总和 = 3

但如果你以为 count() “就是一个值”，把它替换掉，比如替成 1：

1 + 1

得到 2，就错了。

所以 count() 不是引用透明的表达式。
原因就是它有副作用。

环境配置

下载/安装解释器

建议在MacOS，Linux(WSL)系统上运行Ocaml。

依次运行以下命令即可下载Ocaml及其相关工具：

Linux：

# 1. 更新系统包索引
sudo apt update

# 2. 安装 opam（OCaml 的包管理器）
sudo apt install opam -y

# 3. 初始化 opam（首次运行会创建配置文件）
opam init -y --bare

# 4. 加载 opam 环境变量（将 ocaml 等命令加入 PATH）
eval $(opam env)

# 5. 创建指定版本的 OCaml 编译环境（这里是 4.14.1）
opam switch create 4.14.1

# 6. 再次加载 opam 环境（进入新 switch）
eval $(opam env)

# 7. 安装配套工具（dune 构建工具，utop REPL，ocaml-lsp-server 语言服务）
opam install -y dune utop ocaml-lsp-server

MacOS：

# 0. 安装 Homebrew（如果已经安装可以跳过）
/bin/bash -c "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/HEAD/install.sh)"
brew update

# 1. 安装 OCaml 和 OPAM（OCaml 的官方包管理工具）
brew install ocaml opam

# 2. 初始化 OPAM（第一次使用时必须）
opam init
eval $(opam env)

# 3. 创建一个新的 OCaml 编译器环境（可指定版本）
opam switch create 4.14.1
eval $(opam env)

# 4. 安装 utop（更好的 OCaml REPL 工具）
opam install utop
eval $(opam env)

# 5. 启动 utop 测试
utop

其中utop 是 OCaml 的一个增强型交互式命令行（REPL），提供语法高亮、自动补全和更友好的开发体验：

在utop中：

# 表示Interpreter在等待输入（input）；
;; 用于标志一个表达式的结束，告诉解释器可以开始执行（跟C语言中的;一样）；

但在写代码文件时则不需要。
- 则表示输出的结果

关于自动补全的部分，可以使用Alt+Left以及Alt+Right来选择，然后使用Alt+Down进行确认。（这里的Left, Right, Down指的是键盘上的方向键。）

在后续内容中我们（有可能）会utop的格式来区分代码以及结果。

插件

1. OCaml Platform

在VS Code里装OCaml Platform插件后，可以打开 OCaml 文件，选中一段代码，然后用：

1	Shift + Enter

或者命令面板里的：

1	OCaml: Evaluate Selection

把选中的OCaml代码发送到REPL/utop里运行，方便后续在REPL/utop里测试。

2. OCaml LSP

提供自动补全、类型提示、跳转定义、报错提示。

安装：

1	opam install ocaml-lsp-server

有些时候会遇到像这样第一行报错的情况：

这个问题属于OCaml LSP已经启动了，但它不知道这个 src/assignment.ml 属于哪个dune项目，所以自动补全、类型推断会不完整或乱跳。

这个时候需要在src/所在的目录下（不是src/，是上一层）运行：

1	dune build

然后在VS Code里Ctrl+Shift+P后运行

1	OCaml: Restart Language Server

就好了。

3\. ocamlformat

负责自动排版，比如把代码缩进、换行、空格统一成标准风格。

安装：

1	opam install ocamlformat

更新

# 1.确认是通过 opam 管理的 OCaml
opam --version

# 2. 用 opam 安装 OCaml 5.3
opam update
opam upgrade
opam switch create 5.3.0 ocaml-base-compiler.5.3.0

验证：

1 2	$ ocaml -version The OCaml toplevel, version 5.3.0

然后需要重新安装utop：

1	opam install utop

验证：

1 2	utop # Sys.ocaml_version;; - : string = "5.3.0"

Basics

Hello World

1	print_string "Hello World!";;

声明/定义变量

使用let：

1	let <identifier> = <expression>

# let seven = 3+4;;
val seven : int = 7

# seven;;
- : int = 7

变量名的开头需为小写字母。

也可以定义tuple：

1
2
3

let (x,y) = (3,4.0)

let (_,y) = (3,4)

_表示anaonymous variable。

Records

在 OCaml 中，记录（records）是一种 静态、固定字段名 的数据结构，类似于 C 语言的 struct 或 Python 的类实例。

字段名和类型在定义时就固定了，不能动态添加或删除。

跟字典不一样。

type person = {given:string; sur:string; age:int}

let paul = { given="Paul"; sur="Meier"; age=24 }

let hans = { sur="kohl"; age=23; given="hans"}

let hansi = {age=23; sur="kohl"; given="hans"}

# hans = hansi;;
- : bool = true

利用component的名字来访问，比如说

1 2	# paul.given;; - : string = "Paul"

或者利用pattern matching

# let {given = x;sur = y; age = z} = paul;;
val x : string = "Paul"
val ny : string = "Meier"
val z : int = 24

1 2	# let {given = x;_} = paul;; val x : string = "Paul"

Lists 列表

使用[]和::构造列表：

# let mt = [];;
val mt : 'a list = []

# let l1 = 1::mt;;
val l1 : int list = [1]

# let l = [1;2;3];;
val l : int list = [1; 2; 3]

# let l = 1::2::3::[];;
val l : int list = [1; 2; 3]

注意，列表里的所有元素都需要是同一个type的。

我们可以针对一个列表进行pattern matching:

# match l
with 
[] -> -1
| x::xs -> x;;

-: int = 1

其中x指的是当前列表中的第一个元素，而xs是所有剩余的元素。

在 OCaml 里，:: 是 列表拆分（cons）运算符，模式的语法是：

1	head::tail

head部分默认是列表的第一个元素，tail则是剩余。（这里的变量名无关紧要，x::xs, head::tail的效果是完全一样的）

Case Distinction 分类讨论（match\if）

使用match和if：

match n 
with
  | 0 -> "null"
  | 1 -> "one"
  | _ -> "uncountable!"

1
2
3

match e with
| true -> e1
| false -> e2

第二个也可以写成

1	if e then e1 else e2

可以把Ocaml里的match理解成一个分段函数，将不同的定义域上的值映射到其他值上。

也可以把match理解成if, else，其中_为else。

注意写match ... with时需要写一个兜底的case，或者确保写的这些case已经能覆盖全部情况。

Guard

在 OCaml 的match ... with里，guard 就是写在pattern后面的额外条件，形式是：

1	\| pattern when condition -> expression

意思是：先看值能不能匹配这个 pattern；如果能，再检查 when 后面的布尔条件；只有条件为 true，这个分支才会被选中。

例子：

let sign n =
  match n with
  | _ when n > 0 -> "positive"
  | _ when n = 0 -> "zero"
  | _ -> "negative"

更常见的是和变量绑定一起用：

let describe xs =
  match xs with
  | [] -> "empty"
  | [x] when x > 0 -> "one positive element"
  | [x] -> "one non-positive element"
  | _ -> "many elements"

定义类型（Type）

定义Tuple的数据类型：

1
2
3

type vector3 = float*float*float;;

let p1: vector3 = (1.0,1.0,1.0);;

错误示例：

1
2
3

type vector3 = (x1:float; x2:float; x3:float);;

let p1 = vector3(1.0,1.0,1.0);;

type student = {
  first_name : string;
  last_name : string;
  id : int;
  semester : int;
  grades : (int * float) list;
}

type database = student list

数据类型转换

1
2
3

string_of_float
string_of_int
...

异常（Exception）

OCaml里的异常本质上也是构造器类型 exn 的值。

定义异常：

1 2	exception New exception Newer of int

抛出异常：raise

用 raise 抛出异常：

raise New

raise 表达式可以有任意类型，因为它不会正常返回值。比如：

1 2	let f x y = if x then y else raise New

捕获异常：try … with

异常用 try ... with 捕获：

try 
  (if ... else raise New)
with
  | New -> ()

try 
  (if ... else raise (Newer 7) )
with
  | Newer x -> x

触发异常了的话最后返回的结果会是7。

函数

同样使用let来定义函数：（所以在Ocaml里可以把函数理解成变量）

# let double x = 2 * x;;
val double : int -> int = <fun>

# (double 3, douoble (double 1));;
- : int * int = (6,4)

最好直接声明输入的数据类型：

1	let square (x:int) = x*x

:int：声明只接受整数x作为输入。

也可以写成

1 2	# let double = fun x -> 2*x;; val double : int -> int = <fun>

用fun来强调一下这里定义的是一个函数。

不过要注意一点，如果在定义函数时用到了一个之前定义的变量，那么在定义完函数之后修改这个变量并不会修改这个函数的操作。

# let factor = 2;;
val factor : int = 2

# let double x = factor * x;;
val double : int -> int = <fun>

# let factor = 4;;
val factor : int = 4

# double 3;;
- : int = 6

注意到这里的结果是6（$2\cdot3$）而不是12（$4\cdot3$）。

函数类型

先看这个例子：

1
2
3

type 'a t = 'a list = [] | (::) of 'a * 'a list

fold_left : ('a -> 'b -> 'a) -> 'a -> 'b t -> 'a

（这个函数的具体功能后面会讲。）

根据type的定义，它等于：

1	fold_left : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a

这样理解：

这个函数会接收三个参数作为输入，并返回一个输出。输入的内容的公式分别为：

('a -> 'b -> 'a)：一个函数，接收2个输入，返回一个输出。输出的数据类型与输入的第一个参数的数据类型相同；
'a：一个任意类型的数据；
'b list：一个任意数据类型的列表；

而输出的数据类型为'a，与第二个参数相同。

Recursive Functions 递归函数

使用rec：

# let rec fac n = if n < 2 then 1 else n * fac (n-1);;
val fac : int -> int = <fun>

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

val fib : int -> int = <fun>

想要几个新定义的函数交叉引用递归的话则需要用and连接：

# let rec even n = 
if n=0 then "even"
else odd (n-1)
and odd n = 
if n=0 then "odd"
else ecen (n-1);;

val even : int -> string = <fun>
val odd : int -> string = <fun>

使用Case Distinction来定义函数

# let rec length = fun l -> match l with
| [] -> 0
| x:xs -> 1 + length xs;;

val length : 'a list -> int = <fun>

# length [1;2;3];;
- : int = 3

也可以写成

# let rec length = function
| [] -> 0
| x:xs -> 1 + length xs;;

val length : 'a list -> int = <fun>

# length [1;2;3];;
- : int = 3

Local Definitions

可以使用let或者let rec定义一个局部变量（不过需要配合in一起使用）：

# let x = 5 in
let sq = x*x in
sq + sq;;
- : int = 50


# let facin n = 
    let rec iter m yet = 
      if m > n then yet
      else iter (m+1) (m*yet) in
    iter 2 1;;
val facit : int -> int = <fun>

在facin的例子里，我们相当于在定义facin这个函数时定义并调用了一个新函数（iter）。

Tail Recursive 尾递归

我们拿阶乘来举例子，正常的是这么写递归：

1
2
3

let rec fac n =
if n <= 1 then 1
else n * fac (n-1);;

这样子的计算逻辑便是：

fac 5
= 5 * fac 4
= 5 * (4 * fac 3)
= ...

每次都需要递归下去直到得到fac 1的结果了之后再一层一层地乘回来，这样会导致所需的栈空间非常大。

而尾递归的写法则是：

let fac x =
  let rec facit n acc =
    if n <= 1 then acc
    else facit (n - 1) (n * acc)
  in
  facit x 1

这样的流程则变成了：

1	facit 5 1 → facit 4 5 → facit 3 20 → facit 2 60 → facit 1 120 → 返回 120

相当于是一条路走下去。

用汇编的角度来理解就是，普通的情况需要一直call，但是尾递归的写法就只需要jump了。

再来多看些例子：

列表长度

普通递归：

let rec length lst =
  match lst with
  | [] -> 0
  | _ :: t -> 1 + length t

尾递归：

let length lst =
  let rec aux lst len =
    match lst with
    [] -> len
    |_::t -> aux t (len+1)
  in
  aux lst 0;;

列表反转

普通递归：

let rec rev lst =
  match lst with
  | [] -> []
  | h :: t -> (rev t) @ [h]

尾递归：

let rev lst =
  let rec aux lst l =
    match lst with
    [] -> l
    |x::xs -> aux xs (x::l)
  in
  aux lst [];;

列表映射

普通递归：

let rec map f lst =
  match lst with
  | [] -> []
  | h :: t -> (f h) :: (map f t)

尾递归：

let map f lst =
  let rec aux f lst l =
    match lst with
    []-> List.rev l
    |x::xs -> aux f xs ((f x)::l)
  in
  aux f lst [];;

计算树的和

树的Type定义

1	type tree = \| Leaf of int \| Node of int * tree * tree

普通递归：

1
2
3

let rec sum_tree t = match t with 
    | Leaf n -> n 
    | Node(n, left, right) -> n + sum_tree left + sum_tree right

尾递归：

let sum_tree t =
let rec aux  s l =
match l with
[] -> s
|Leaf n :: xs -> aux (s+n) xs
|Node(n,left,right)::xs -> aux (s+n) (left::right::xs)
in
aux 0 [t];;

核心思路：将left和right tree全都添加进一个列表里，等后续慢慢处理。

总结一下如何快速判断一个函数是否是尾递归的：

如果在调用它时，需要利用其结果再进行任何计算，那都属于非尾递归，比如说

1
2
3

n * fac (n-1)

n + sum_tree left + sum_tree right

而如果调用时干净利落，前后没有跟任何多余的东西，则属于尾递归，比如说：

1
2
3

facit (n - 1) (n * acc)

aux (s+n) (left::right::xs)

List函数

先看一下全部的签名（4.14.1版本下的）：

# #show List;;
module List :
  sig
    type 'a t = 'a list = [] | (::) of 'a * 'a list
    val length : 'a t -> int
    val compare_lengths : 'a t -> 'b t -> int
    val compare_length_with : 'a t -> int -> int
    val cons : 'a -> 'a t -> 'a t
    val hd : 'a t -> 'a
    val tl : 'a t -> 'a t
    val nth : 'a t -> int -> 'a
    val nth_opt : 'a t -> int -> 'a option
    val rev : 'a t -> 'a t
    val init : int -> (int -> 'a) -> 'a t
    val append : 'a t -> 'a t -> 'a t
    val rev_append : 'a t -> 'a t -> 'a t
    val concat : 'a t t -> 'a t
    val flatten : 'a t t -> 'a t
    val equal : ('a -> 'a -> bool) -> 'a t -> 'a t -> bool
    val compare : ('a -> 'a -> int) -> 'a t -> 'a t -> int
    val iter : ('a -> unit) -> 'a t -> unit
    val iteri : (int -> 'a -> unit) -> 'a t -> unit
    val map : ('a -> 'b) -> 'a t -> 'b t
    val mapi : (int -> 'a -> 'b) -> 'a t -> 'b t
    val rev_map : ('a -> 'b) -> 'a t -> 'b t
    val filter_map : ('a -> 'b option) -> 'a t -> 'b t
    val concat_map : ('a -> 'b t) -> 'a t -> 'b t
    val fold_left_map : ('a -> 'b -> 'a * 'c) -> 'a -> 'b t -> 'a * 'c t
    val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b t -> 'a
    val fold_right : ('a -> 'b -> 'b) -> 'a t -> 'b -> 'b
    val iter2 : ('a -> 'b -> unit) -> 'a t -> 'b t -> unit
    val map2 : ('a -> 'b -> 'c) -> 'a t -> 'b t -> 'c t
    val rev_map2 : ('a -> 'b -> 'c) -> 'a t -> 'b t -> 'c t
    val fold_left2 : ('a -> 'b -> 'c -> 'a) -> 'a -> 'b t -> 'c t -> 'a
    val fold_right2 : ('a -> 'b -> 'c -> 'c) -> 'a t -> 'b t -> 'c -> 'c
    val for_all : ('a -> bool) -> 'a t -> bool
    val exists : ('a -> bool) -> 'a t -> bool
    val for_all2 : ('a -> 'b -> bool) -> 'a t -> 'b t -> bool
    val exists2 : ('a -> 'b -> bool) -> 'a t -> 'b t -> bool
    val mem : 'a -> 'a t -> bool
    val memq : 'a -> 'a t -> bool
    val find : ('a -> bool) -> 'a t -> 'a
    val find_opt : ('a -> bool) -> 'a t -> 'a option
    val find_map : ('a -> 'b option) -> 'a t -> 'b option
    val filter : ('a -> bool) -> 'a t -> 'a t
    val find_all : ('a -> bool) -> 'a t -> 'a t
    val filteri : (int -> 'a -> bool) -> 'a t -> 'a t
    val partition : ('a -> bool) -> 'a t -> 'a t * 'a t
    val partition_map : ('a -> ('b, 'c) Either.t) -> 'a t -> 'b t * 'c t
    val assoc : 'a -> ('a * 'b) t -> 'b
    val assoc_opt : 'a -> ('a * 'b) t -> 'b option
    val assq : 'a -> ('a * 'b) t -> 'b
    val assq_opt : 'a -> ('a * 'b) t -> 'b option
    val mem_assoc : 'a -> ('a * 'b) t -> bool
    val mem_assq : 'a -> ('a * 'b) t -> bool
    val remove_assoc : 'a -> ('a * 'b) t -> ('a * 'b) t
    val remove_assq : 'a -> ('a * 'b) t -> ('a * 'b) t
    val split : ('a * 'b) t -> 'a t * 'b t
    val combine : 'a t -> 'b t -> ('a * 'b) t
    val sort : ('a -> 'a -> int) -> 'a t -> 'a t
    val stable_sort : ('a -> 'a -> int) -> 'a t -> 'a t
    val fast_sort : ('a -> 'a -> int) -> 'a t -> 'a t
    val sort_uniq : ('a -> 'a -> int) -> 'a t -> 'a t
    val merge : ('a -> 'a -> int) -> 'a t -> 'a t -> 'a t
    val to_seq : 'a t -> 'a Seq.t
    val of_seq : 'a Seq.t -> 'a t
  end

5.3.0版本下的全部的签名：

utop # #show List;;
module List :
  sig
    type 'a t = 'a list = [] | (::) of 'a * 'a list
    val length : 'a t -> int
    val compare_lengths : 'a t -> 'b t -> int
    val compare_length_with : 'a t -> int -> int
    val is_empty : 'a t -> bool
    val cons : 'a -> 'a t -> 'a t
    val hd : 'a t -> 'a
    val tl : 'a t -> 'a t
    val nth : 'a t -> int -> 'a
    val nth_opt : 'a t -> int -> 'a option
    val rev : 'a t -> 'a t
    val init : int -> (int -> 'a) -> 'a t
    val append : 'a t -> 'a t -> 'a t
    val rev_append : 'a t -> 'a t -> 'a t
    val concat : 'a t t -> 'a t
    val flatten : 'a t t -> 'a t
    val equal : ('a -> 'a -> bool) -> 'a t -> 'a t -> bool
    val compare : ('a -> 'a -> int) -> 'a t -> 'a t -> int
    val iter : ('a -> unit) -> 'a t -> unit
    val iteri : (int -> 'a -> unit) -> 'a t -> unit
    val map : ('a -> 'b) -> 'a t -> 'b t
    val mapi : (int -> 'a -> 'b) -> 'a t -> 'b t
    val rev_map : ('a -> 'b) -> 'a t -> 'b t
    val filter_map : ('a -> 'b option) -> 'a t -> 'b t
    val concat_map : ('a -> 'b t) -> 'a t -> 'b t
    val fold_left_map :
      ('acc -> 'a -> 'acc * 'b) -> 'acc -> 'a t -> 'acc * 'b t
    val fold_left : ('acc -> 'a -> 'acc) -> 'acc -> 'a t -> 'acc
    val fold_right : ('a -> 'acc -> 'acc) -> 'a t -> 'acc -> 'acc
    val iter2 : ('a -> 'b -> unit) -> 'a t -> 'b t -> unit
    val map2 : ('a -> 'b -> 'c) -> 'a t -> 'b t -> 'c t
    val rev_map2 : ('a -> 'b -> 'c) -> 'a t -> 'b t -> 'c t
    val fold_left2 : ('acc -> 'a -> 'b -> 'acc) -> 'acc -> 'a t -> 'b t -> 'acc
    val fold_right2 :
      ('a -> 'b -> 'acc -> 'acc) -> 'a t -> 'b t -> 'acc -> 'acc
    val for_all : ('a -> bool) -> 'a t -> bool
    val exists : ('a -> bool) -> 'a t -> bool
    val for_all2 : ('a -> 'b -> bool) -> 'a t -> 'b t -> bool
    val exists2 : ('a -> 'b -> bool) -> 'a t -> 'b t -> bool
    val mem : 'a -> 'a t -> bool
    val memq : 'a -> 'a t -> bool
    val find : ('a -> bool) -> 'a t -> 'a
    val find_opt : ('a -> bool) -> 'a t -> 'a option
    val find_index : ('a -> bool) -> 'a t -> int option
    val find_map : ('a -> 'b option) -> 'a t -> 'b option
    val find_mapi : (int -> 'a -> 'b option) -> 'a t -> 'b option
    val filter : ('a -> bool) -> 'a t -> 'a t
    val find_all : ('a -> bool) -> 'a t -> 'a t
    val filteri : (int -> 'a -> bool) -> 'a t -> 'a t
    val take : int -> 'a t -> 'a t
    val drop : int -> 'a t -> 'a t
    val take_while : ('a -> bool) -> 'a t -> 'a t
    val drop_while : ('a -> bool) -> 'a t -> 'a t
    val partition : ('a -> bool) -> 'a t -> 'a t * 'a t
    val partition_map : ('a -> ('b, 'c) Either.t) -> 'a t -> 'b t * 'c t
    val assoc : 'a -> ('a * 'b) t -> 'b
    val assoc_opt : 'a -> ('a * 'b) t -> 'b option
    val assq : 'a -> ('a * 'b) t -> 'b
    val assq_opt : 'a -> ('a * 'b) t -> 'b option
    val mem_assoc : 'a -> ('a * 'b) t -> bool
    val mem_assq : 'a -> ('a * 'b) t -> bool
    val remove_assoc : 'a -> ('a * 'b) t -> ('a * 'b) t
    val remove_assq : 'a -> ('a * 'b) t -> ('a * 'b) t
    val split : ('a * 'b) t -> 'a t * 'b t
    val combine : 'a t -> 'b t -> ('a * 'b) t
    val sort : ('a -> 'a -> int) -> 'a t -> 'a t
    val stable_sort : ('a -> 'a -> int) -> 'a t -> 'a t
    val fast_sort : ('a -> 'a -> int) -> 'a t -> 'a t
    val sort_uniq : ('a -> 'a -> int) -> 'a t -> 'a t
    val merge : ('a -> 'a -> int) -> 'a t -> 'a t -> 'a t
    val to_seq : 'a t -> 'a Seq.t
    val of_seq : 'a Seq.t -> 'a t
  end

List.fold_left

语法：

1	List.fold_left f acc lst

f：是一个“累积函数”，定义如何处理当前元素和累积值。
它的类型是 ('b -> 'a -> 'b)，即接收当前累积值和当前元素，返回新的累积值。（顺序一定不能反）

（ (acc, list_element) -> new_acc）
acc：是初始累积值（'b）。
lst：是要处理的列表（'a）。
从列表的左边开始，依次用 f 更新累积值。

例子：

用于实现之前的列表映射函数map：

1 2	let map f lst = List.rev (List.fold_left (fun acc x -> (f x) :: acc) lst []);;

List.fold_left

语法：

1	List.fold_right f lst acc

f：'a -> 'b -> 'b（ (list_element, acc) -> new_acc）
lst：'a
acc：'b
从列表的右边开始，依次用f更新累积值。

List.rev

定义：

1	List.rev : 'a list -> 'a list

返回一个反转后的列表。

示例：

1 2	List.rev [1; 2; 3];; (* 结果: [3; 2; 1] *)

List.map

定义：

1	List.map : ('a -> 'b) -> 'a list -> 'b list

对列表中每个元素应用函数，按原顺序生成等长的新列表。

示例：

List.map (fun x -> x * x) [1; 2; 3];;
(* 结果: [1; 4; 9] *)

List.map String.length ["ab"; "c"; "def"];;
(* 结果: [2; 1; 3] *)

List.filter

语法：

1	List.filter (fun x -> condition) list

List.filter：用于从列表中挑选符合条件的元素。
参数：
- fun x -> condition：一个函数，对列表中的每个元素 x 判断是否满足条件（condition 是布尔表达式）。
- list：要过滤的列表。
返回值：一个新列表，包含原列表中所有满足条件的元素。

List.length

语法：

1	List.length list

List.length：用于计算列表中元素的个数。
参数：
- list：要计算长度的列表。
返回值：一个 int 类型的整数，表示列表中元素的数量。

例子：

1	List.length [1; 2; 3]

List.flatten/List.concat

定义：

1	List.flatten : 'a list list -> 'a list

把列表的列表（List of lists）按顺序拼接为一个列表。

示例：

List.flatten [[1; 2]; []; [3]; [4; 5]];;
(* 结果: [1; 2; 3; 4; 5] *)

List.flatten [["ab"; "cd"]; ["ef"]];;
(* 结果: ["ab"; "cd"; "ef"] *)

List.concat_map

定义：

1	List.concat_map : ('a -> 'b list) -> 'a list -> 'b list

“先映射、再拍平”的组合。
List.concat_map f xs 等价于 List.flatten (List.map f xs)。

示例：

List.concat_map (fun x -> [x; x * x]) [1; 2; 3];;
(* 结果: [1; 1; 2; 4; 3; 9] *)

List.concat_map (fun s -> List.of_seq (String.to_seq s)) ["ab"; "cd"];;
(* 结果: ['a'; 'b'; 'c'; 'd'] *)

List.cons

定义：

1	List.cons : 'a -> 'a list -> 'a list

也就是 :: 运算符的函数形式：把一个元素放到一个列表的前面（即“构造”一个新列表）。

示例：

1 2	List.cons 1 [2;3];; (* 结果: [1;2;3] *)

相当于：

1	1 :: [2;3]

List.take

定义：

1	List.take : int -> 'a list -> 'a list

（来源： https://ocaml.org/manual/5.3/api/List.html 。5.3版本里也有。）

取出列表前 n 个元素，如果列表长度小于 n，就返回整个列表。

示例：

1 2	List.take [10;20;30;40] 2;; (* 结果: [10;20] *)

List.nth

定义：

1	List.nth : 'a list -> int -> 'a

从列表中取出第 n 个元素（0-based），如果越界则抛异常。

示例：

1 2	List.nth ["a";"b";"c"] 1;; (* 结果: "b" *)

List.exists

定义：

1	List.exists : ('a -> bool) -> 'a list -> bool

1	List.exists 条件函数列表

1
2
3

List.exists (fun x -> x > 3) [1; 2; 5; 0]

(* 结果: true *)

树（Trees）

Rose Trees

多叉树：

1	type tree = T of tree list

计算树的节点数：

1 2	let rec size (T ts) = List.fold_left (+) 1 (List.map size ts)

当前根节点贡献 1；
List.map size ts 递归计算每棵子树的大小，得到一个整数列表；
List.fold_left (+) 1 ... 把这些子树大小全部加起来。

检查子树：

1 2	let rec isSubtree t (T ts) = (t = T ts) \|\| List.exists (isSubtree t) ts

计算深度：

1 2	let rec depth (T ts) = 1 + List.fold_left Int.max (-1) (List.map depth ts)

Pre-Ordering和Post-ordering：

Pre-Order：

1 2	let rec presubtrees (T ts) = List.fold_left (fun tr t -> tr @ (presubtrees t)) [T ts] ts

Post-Order：

1 2	let rec postsubtrees (T ts) = List.fold_right (fun t tr -> (postsubtrees t) @ tr) ts [T ts]

Labeled Trees

树的每个节点还带有一个值/标签：

1	type 'a ltree = L of 'a * 'a ltree list

一个节点由“标签值 + 子树列表”组成。

取根节点标签：

1	let head (L (x, _)) = x

去掉所有标签，只保留树的形状 / 转成普通的树：

1 2	let rec shape (L (_, ts)) = T (map shape ts)

按前序遍历（Pre-Order）找到第一个满足条件 p 的标签：

let rec find p (L (x, ts)) =
  let rec finds = function
    | [] -> None
    | t :: tr ->
      match find p t with
        | Some x -> Some x
        | None -> finds tr
  in
  if p x then Some x else finds ts

对树中所有标签应用函数 f，保持树结构不变：

1 2	let rec lmap f (L (x, ts)) = L (f x, List.map (lmap f) ts)

Balanced Trees

如果一棵树所有叶子的地址长度都相同，那么它是 balanced。换句话说，所有叶子在同一层。

Module

open：

open只是让名字在当前作用域里可直接使用，不会把这些定义变成当前模块的导出内容。

module A = struct let x = 1 end
(*module A : sig val x : int end*)

module B =
struct
  open A
  let y = 2
end
(*module B : sig val y : int end*)

include：

include会把另一个模块的定义包含进当前模块。

module C =
struct
  include A
  include B
end
(*module C : sig val x : int val y : int end*)

Ocaml 入门

函数式编程（Functional Programming）

Data is immutable：数据不可变

Pure functions have no side effects：纯函数没有副作用

Referential transparency：引用透明

环境配置

下载/安装解释器

插件

更新

Basics

Hello World

声明/定义变量

Records

Lists 列表

Case Distinction 分类讨论（match\if）

Guard

定义类型（Type）

数据类型转换

异常（Exception）

函数

函数类型

Recursive Functions 递归函数

使用Case Distinction来定义函数

Local Definitions

Tail Recursive 尾递归

列表长度

列表反转

列表映射

计算树的和

List函数

List.fold_left

List.fold_left

List.rev

List.map

List.filter

List.length

List.flatten/List.concat

List.concat_map

List.cons

List.take

List.nth

List.exists

树（Trees）

Rose Trees

Labeled Trees

Balanced Trees

Module

Signature

Functor

ToyCaml

静态语义（Static semantics）

动态语义（Dynamic Semantics）