OCaml 学习笔记
该笔记主要是基于 OCaml Programming: Correct + Efficient + Beautiful 和 OCaml 语言编程基础教程 这两本书，还有 Real World OCaml，以及一些官网的资料，留下的一些学习记录，顺序可能和这些书都不完全一样，内容也可能不会很全面，需要学习最好还是配合这几本书。
目前第一本书是只有英文的，是康奈尔大学的教材，比较适合入门；第二本则是国内作者编写的，也可以用作入门使用；而第三本书则是相当于高级篇，最新的是第二版的，中文只有第一版的，内容会更有深度。
Part 1 - 环境配置与基本用法
1.1 - 环境配置
官网提供了基本的安装教程，照着做就行了，不过对于 Windows，我并不推荐使用 Diskuv OCaml 这个发行版，而是建议使用 WSL2 按照 Linux 的方法来，不过可能会遇到一些网络问题。
官方还提供了一个在 Windows 安装的教程，按照目前（2023年11月）的内容，还未提供原生的 Windows 支持，估计 2024 年会提供这个支持。
如果按照官网的教程在 WSL2 或 Linux 安装出现问题，建议改善网络条件，或者可以通过 Linux 发行版的包管理器安装一个 opam，例如在 Debian 系可以使用 sudo apt install opam 来进行安装，安装之后首先需要使用 opam init执行初始化命令（记得允许添加到 PATH），之后则可以通过 opam switch create xxx 来创建一个编译器，其中的 “xxx” 是版本号，具体可以通过 opam switch list-available 查看，建议 ocaml-base-compiler 字段的版本号。比如 opam switch create 5.1.0 就会下载并安装一个 5.1.0 的 OCaml 编译器，这个过程比较慢，需要等一段时间。
比如这是一次安装的输出内容：
<><> Installing new switch packages <><><><><><><><><><><><><><><><><><><><><><>
Switch invariant: ["ocaml-base-compiler" {= "5.1.0"} | "ocaml-system" {= "5.1.0"}]
<><> Processing actions <><><><><><><><><><><><><><><><><><><><><><><><><><><><>
∗ installed base-bigarray.base
∗ installed base-threads.base
∗ installed base-unix.base
∗ installed ocaml-options-vanilla.1
⬇ retrieved ocaml-base-compiler.5.1.0 (https://opam.ocaml.org/cache)
∗ installed ocaml-base-compiler.5.1.0
∗ installed ocaml-config.3
∗ installed ocaml.5.1.0
∗ installed base-domains.base
∗ installed base-nnp.base
Done.
# Run eval $(opam env --switch=5.1.0) to update the current shell environment
记得按照最后一行的内容执行一下 eval $(opam env) 命令。
如果安装了多个编译器，可以通过 opam switch list 命令（或者直接 opam switch，因为默认就是）查看，通过 opam switch set xxx 切换一个版本。
之后按照官网，使用
opam install dune merlin ocaml-lsp-server odoc ocamlformat utop dune-release
来安装必要的工具，其中需要注意的是 utop 和 dune，这俩在之后是一直要用的，其他的主要在编辑器用到的多。其中 utop 是 REPL 的一个顶层实现，类似于 python 的交互式环境。其实直接在终端执行 ocaml 就是基础的顶层，不过 utop 明显更加强大。不过所有的开发都在顶层是不现实的，因此需要使用构建系统 dune 来进行开发。
注意上述操作对于每一个 switch 都是独立的，因为这些工具的管理器 opam 是基于源码的，所以需要根据当前编译器进行编译。一般每个大版本保留一个最新发布的稳定版编译器就行了，比如目前的 5.1.x 版本以及稍早的 4.14.x 版本（当然学习来说最新的就可以了）。
对于编辑器，可以使用 Vim 和 Emacs 这种传统的，也可以用这些年最流行的 Visual Studio Code。对于 Windows 环境，建议使用 vscode 搭配 WSL 插件，并在虚拟机安装 OCaml Platform 插件来使用。
1.2 - 基本使用
直接在终端运行 utop 即可进入顶层，如果提示没有安装请检查 opam 是否安装成功。
输入一些基本的加减乘除运算，在最后使用两个连续的分号再按下回车就会执行。例如 1 + 1;; 就是一句有效的算术命令。
注意顶层的每一个输入都需要以两个分号结尾，表示这是一个表达式。退出顶层的方法则是输入 #quit;; 并回车。
对于使用文件的操作，可以新建一个叫 “hello.ml” 的文件并输入如下内容：
let _ = print_endline "Hello, World!"
这里的 let _ 也可以换成 let ()，效果是一样的（当然原理不一样，在 utop 试试看区别）。
使用命令 ocaml hello.ml 即可运行并输出指定的字符串。
注意在文件写的代码不需要在结尾和语句之间加两个分号的，那是顶层特定的要求。
还可以使用 dune 工具创建一个项目，例如使用命令 dune init project hello 就会在当前目录创建一个子目录 “hello” 并在内部生成一系列的文件。使用 tree hello 命令可以查看目录结构：
hello
├── bin
│ ├── dune
│ └── main.ml
├── dune-project
├── hello.opam
├── lib
│ └── dune
└── test
├── dune
└── hello.ml
其中的源代码就放在了 “hello/bin/main.ml” 里面，默认就是一句打印 “Hello, World!” 的内容。
使用 dune exec hello 就可以构建并运行这个项目了。
Part 2 - 语言基础知识
2.1 - 基本类型
int 类型
在 utop 顶层输入任意整数加两个分号，就可以得到最基本的整数类型了。
utop # 52;;
- : int = 52
整数定义时可以用下划线来分割，从视觉上来好看一些：
utop # 1_000;;
- : int = 1000
utop # 5_2000;;
- : int = 52000
整数有加减乘除模这5种基本运算符：
utop # 1 + 1;;
- : int = 2
utop # 1 - 1;;
- : int = 0
utop # 2 * 2;;
- : int = 4
utop # 5 / 2;;
- : int = 2
utop # 5 mod 2;;
- : int = 1
这些和大多数语言都是类似的。
还可以通过 max_int;; 还有 min_int;; 获取整数的表示范围：
utop # max_int;;
- : int = 4611686018427387903
utop # min_int;;
- : int = -4611686018427387904
可以看到实际上的范围是 -2^62^ 到 2^62^ ，而不是一般认为的 2^63^ ，当然这都是对于 64 位来说的，对于 32 位则是 2^30^ 了。不过目前大多数使用的系统都是 64 位，所以通常就是上述的结果。
整数还可以使用二进制、八进制和十六进制表示，和其他很多语言是差不多的：
utop # 0b110100;;
- : int = 52
utop # 0o64;;
- : int = 52
utop # 0x34;;
- : int = 52
和很多语言一样，0b 0o 0x 和 0B 0O 0X 是一样的，也就是前缀不区分大小写。
除了上述默认的 int 类型，还有 int32 和 int64 这两个和标准的整数类型，使用方法是后缀 l(小写的L) 以及 L。
utop # 52l;;
- : int32 = 52l
utop # 52L;;
- : int64 = 52L
注意上述的三种整数类型不能直接混合使用，需要使用相应的函数转换，一般的原则是转换到宽度最大的。
utop # Int64.add 52L (Int64.of_int32 52l);;
- : int64 = 104L
utop # Int64.add 52L (Int64.of_int 52);;
- : int64 = 104L
这里涉及到函数调用，后面有说明。
float 类型
浮点数的基本表示法如下：
utop # 52.;;
- : float = 52.
utop # 52.666;;
- : float = 52.666
utop # 5.2e1;;
- : float = 52.
utop # 52E0;;
- : float = 52.
运算和 int 差不多，但是需要在运算符后面加一个点（mod 则是需要调用函数 mod_float）：
utop # 1. +. 1.;;
- : float = 2.
utop # 52. /. 10. ;;
- : float = 5.2
utop # mod_float 52. 11.5 ;;
- : float = 6.
混合整数和浮点数的运算需要函数转换，否则无法运行：
utop # float_of_int 52 /. 11.5 ;;
- : float = 4.52173913043478226
使用 max_float 和 min_float 可以查看浮点数的表示范围：
utop # max_float;;
- : float = 1.79769313486231571e+308
utop # min_float;;
- : float = 2.22507385850720138e-308
这也说明了浮点数在 OCaml 是双精度的。
char 类型
OCaml 的 char 和 C 一样，都是只能取值 0 到 255 ，也就是 ASCII 和一些扩展字符。语法也和 C 一样用单引号。
utop # '5' ;;
- : char = '5'
utop # '2' ;;
- : char = '2'
可以用 char_of_int 看编码对应的字符：
utop # char_of_int 112;;
- : char = 'p'
utop # char_of_int 106;;
- : char = 'j'
utop # char_of_int 255;;
- : char = '\255'
utop # char_of_int 256;;
Exception: Invalid_argument "char_of_int".
同理还有 int_of_char 就不细说了。
string 类型
字符串用双引号包裹，中文用 UTF-8 编码：
utop # "52pojie";;
- : string = "52pojie"
utop # "吾爱破解";;
- : string = "吾爱破解"
使用 print_string 可以打印一个字符串，使用 print_endline 还可以顺便加一个换行：
utop # print_string "52pojie";;
52pojie- : unit = ()
utop # print_endline "吾爱破解";;
吾爱破解
- : unit = ()
还有一些常用函数处理字符串：
utop # String.trim " 52 pojie ";;
- : string = "52 pojie"
utop # String.length "吾爱破解";;
- : int = 12
utop # String.get "52pojie" 3;;
- : char = 'o'
utop # String.get "吾爱破解" 3;;
- : char = '\231'
utop # String.contains "52pojie" '2';;
- : bool = true
为了打印或者生成字符串，还有 Printf 模块的一系列函数：
utop # Printf.printf "%dpojie\n" 52;;
52pojie
- : unit = ()
utop # Printf.sprintf "52%s\n" "pojie";;
- : string = "52pojie\n"
unit 类型
注意到前面 print_string 以及 printf 这些函数，其返回值是 - : unit = () 而不是没有返回值。这是因为作为一种函数式语言，OCaml 需要任何函数都有一个返回值，但是一个输出字符串的函数用不着返回值，于是就定义了 unit 类型，相当于无返回。
utop # ();;
- : unit = ()
unit 类型只有一个值，也就是 () ，即一对括号。
unit 类型也可以作为函数的参数，比如：
utop # print_newline ();;
- : unit = ()
注意空号就是打印出了一个换行符。
bool 类型
bool 类型和很多语言一样，只有 true 和 false 这两个值，同时支持一些基本的函数（运算符）：
utop # not false;;
- : bool = true
utop # true || false;;
- : bool = true
utop # true && false;;
- : bool = false
当然还有一些基本的比较运算：
utop # 1 < 2;;
- : bool = true
utop # 1 = 2;;
- : bool = false
更多内容在之后的表达式部分。
2.2 - 表达式
之前基本类型的 int 和 float 类型中就使用了一些基本的表达式，稍微复杂点的就是将它们复合起来。
utop # 1 + 2 + 16;;
- : int = 19
utop # float_of_int 15 +. 2.5 +. 11.5;;
- : float = 29.
let 表达式
let 表达式基本语法是 let v = e ，即将一个表达式 e 求值并绑定（bind）到变量 v 。
utop # let a = 52;;
val a : int = 52
类型推导系统得出了表达式 52 的类型是 int ，之后 a 就暂时代表了 52 这个值。
utop # let b = a + 1;;
val b : int = 53
由于 let 表达式是绑定机制，所以可以重新定义变量 a 。
utop # let a = 50;;
val a : int = 50
utop # b;;
- : int = 53
这不会影响到变量 b ，这是因为 b 在定义的时候已经求值了，不会受 a 的影响。
事实上 a 可以重新绑定到任意类型的值：
utop # let a = "52pojie";;
val a : string = "52pojie"
都不会有影响，这和大多数语言的赋值有本质的区别。
let 表达式还有并行定义的方法：
utop # let a = 1 and b = 2;;
val a : int = 1
val b : int = 2
但是下面是错误的：
utop # let x = 1 and y = x;;
Error: Unbound value x
因为并行定义是不能让 and 后面的表达式依赖之前未定义的变量。
下面的用法就不会出错：
utop # let x = 2;;
val x : int = 2
utop # let x = 1 and y = x;;
val x : int = 1
val y : int = 2
因为在执行 let x = 1 and y = x 的时候，x 已经有了一个值 2 。
let 表达式还能局部定义，语法为 let v = e1 in e2 ，例如：
utop # let x = 2 in x + 2;;
- : int = 4
还可以嵌套使用：
utop # let a = 10 in let b = 20 in a + b;;
- : int = 30
其好处就是 let 表达式绑定的变量只能在局部使用，不会影响全局作用域，类似于局部变量的作用。
let 局部定义也可以并行定义：
utop # let a = 1 in let b = a and a = 2 in a + b;;
- : int = 3
这里还涉及到了局部作用域的概念，和大多数语言一样，局部定义同名变量会暂时遮蔽外部的变量，在离开作用域后效果就会消失。
比较运算符
utop # 1 < 2;;
- : bool = true
utop # 1. > 2.;;
- : bool = false
utop # 'a' = 'b';;
- : bool = false
utop # "abc" <> "abb";;
- : bool = true
和整数运算符 + 以及浮点是运算符 +. 这样有区分不同，比较运算符和类型无关，这是因为类型推断在比较运算符这里是不会有歧义的，而在算术运算那里是有歧义的。
相等和不相等是 = 和 <> ，和一些语言的 == 和 != 不一样。其实在 OCaml 也支持 == 和 != 的，但是有不同的作用。
== 和 != 的意思有两个，一是对于非结构化数据，效果与 = 和 <> 一致；二是对于结构化数据，比较的是变量是否指向同一地址。
整数和字符是非结构化数据，浮点数和字符串是结构化数据。
比如：
utop # 52 = 52;;
- : bool = true
utop # 52 == 52;;
- : bool = true
utop # 'a' = 'a';;
- : bool = true
utop # 'a' == 'a';;
- : bool = true
utop # 1. == 1. ;;
- : bool = false
utop # 1. = 1.;;
- : bool = true
utop # "abc" = "abc";;
- : bool = true
utop # "abc" <> "abc";;
- : bool = false
utop # "abc" == "abc";;
- : bool = false
utop # "abc" != "abc";;
- : bool = true
if 表达式
if 表达式的语法为 if e1 then e2 else e3 ，其中表达式 e1 必须是 bool 类型的，e2 和 e3 必须是同一种类型的，此外 else 部分可选，前提是表达式 e2 是 unit 类型的，这也意味着大多数时候都是带有 else 分支的。
if 表达式和一般命令式语言的 if 表达式不一样，反而是和常见的三目运算符 ?: 效果很相似。例如下面两条代码意思相同：
int a = b > c ? d : e;
let a = if b > c then d else e
if 表达式还可以嵌套，类似于：
let a =
if b > c then d
else if b < c then e
else f
总的来说 if 表达式并没有复杂的语法，相对比较简单。
2.3 - 函数
简单函数
函数的定义非常简单，基本语法为 let f x = e 其中 f 是函数名，x 是参数，e 是表达式，比如说定义一个简单的加一函数：
let inc x = x + 1
utop # let inc x = x + 1;;
val inc : int -> int = <fun>
utop # inc 51;;
- : int = 52
函数的类型是用 t1 -> t2 -> ... tn = <fun> 来标注的，箭头的最后一个类型是返回值的类型，其余是参数列表的类型。
比如定义一个加法函数：
utop # let add a b = a + b;;
val add : int -> int -> int = <fun>
utop # add 51 1;;
- : int = 52
函数的调用方法非常简单，用空格区分每个参数就行了，如果参数存在函数调用需要括号：
utop # add 50 (inc 1);;
- : int = 52
这是因为函数的求值顺序是从左到右。
递归函数
定义递归函数的方法是在 let 后面加一个 rec 关键字：
let rec fact n =
if n = 0 then 1 else n * fact (n - 1)
这是一个简单的求阶乘函数。
utop # let rec fact n = if n = 0 then 1 else n * fact (n - 1);;
val fact : int -> int = <fun>
utop # fact 5 ;;
- : int = 120
utop # fact 10 ;;
- : int = 3628800
使用 let rec ... and ... 可以定义相互递归的函数：
let rec odd n =
n > 0 && even (n - 1)
and even n =
n = 0 || odd (n - 1)
utop #
let rec odd n =
n > 0 && even (n - 1)
and even n =
n = 0 || odd (n - 1);;
val odd : int -> bool = <fun>
val even : int -> bool = <fun>
utop # odd 5;;
- : bool = true
utop # even 5;;
- : bool = false
匿名函数
如果一个函数不绑定到一个名称，就是匿名函数了，匿名函数需要使用关键字 fun 来定义。
utop # fun x -> x + 1;;
- : int -> int = <fun>
匿名函数可以直接调用：
utop # (fun x -> x + 1) 51;;
- : int = 52
也可以把匿名函数绑定到一个名称，这和定义函数是一样的：
utop # let inc1 = fun x -> x + 1;;
val inc1 : int -> int = <fun>
utop # inc1 51;;
- : int = 52
管道操作
管道操作很适合连续调用单参数的简单函数，从而减少括号的数量。
定义平方函数 square 和自增函数 inc 如下：
let square x = x * x
let inc x = x + 1
假设需要按照如下顺序使用：
square (inc (square (inc 52)))
可以看到是非常繁琐的，但是使用管道操作就可以简化操作了：
52 |> inc |> square |> inc |> square
看起来就清晰很多了。
高阶函数
高阶函数就是一种输入参数或者返回值为函数的函数。
定义一个函数 f 如下：
let f g x = g x + x
该函数的参数 g 是一个函数，这个函数的类型通过 g x 推导出了其参数只有 1 个，又因为存在 + 运算符，可以得出 g x 的类型和 x 的类型都是 int ，所以得出函数 g 的类型应该是 int -> int ，于是函数 f 的类型为 (int -> int) -> int -> int 。
对于参数 g ，可以传入一个已有的函数：
utop # let double x = x * 2;;
val double : int -> int = <fun>
utop # f double 5;;
- : int = 15
也可以传入一个匿名函数：
utop # f (fun x -> x + 52) 52;;
- : int = 156
在 C 中类似的操作是将函数指针作为参数。
运算符
其实运算符本身就是一种特殊的函数，当运算符作为函数时，需要用一对括号包裹：
utop # (+);;
- : int -> int -> int = <fun>
但是注意乘法符号 * 加括号时需要留空格：
utop # ( * );;
- : int -> int -> int = <fun>
这是因为在 OCaml 里面，注释的形式是 (* ... *) 这样的。
在运算符周围加入括号可以将运算符当作函数调用：
utop # ( * ) 2 3;;
- : int = 6
而定义一个运算符的方法就是加括号：
let ( % ) a b = a mod b
这样就定义了百分号作为取余数的运算符。
utop # ( % );;
Error: Unbound value %
utop # let ( % ) a b = a mod b;;
val ( % ) : int -> int -> int = <fun>
utop # ( % );;
- : int -> int -> int = <fun>
utop # 52 % 10;;
- : int = 2
运算符可以超过一个符号，就像前面的管道操作一样。
let ( >>> ) x f = f x
这个函数的类型比较复杂（ 'a -> ('a -> 'b) -> 'b = <fun> ），涉及到多态函数。
使用之前定义的 inc 和 square 来测试一下：
utop # 2 >>> inc >>> square >>> inc;;
- : int = 10
多态函数
定义一个函数 add 如下：
let add a b = a + b
由于 + 运算符的参数类型都是 int ，所以可以得出 add 的两个参数的类型都是 int 。
但是如果定义一个这样的函数：
let id x = x
一个简单返回自身的函数，其类型则是 'a -> 'a = <fun> ，其中的 'a 就代表了多态类型，即可以是任意类型。如果类型较多，通常的顺序是 'a 'b 'c ，依次读作 alpha beta gamma ，如果还有更多就不清楚了，理论上可以无限多。
再看之前自己定义的管道运算函数的类型：
utop # let ( >>> ) x f = f x;;
val ( >>> ) : 'a -> ('a -> 'b) -> 'b = <fun>
参数 x 的类型是 'a ；参数 f 要求一个 'a 类型的参数，返回 'b 类型的结果；整个函数的结果就是 'b 类型的。因为对于 f x 调用，不能确定结果是不是和 x 一样，所以就会有另一个类型。
实际上自带的管道操作 |> 其类型和自行定义的 >>> 是一样的。
utop # 52.5 |> int_of_float |> char_of_int;;
- : char = '4'
这就是一个很好的类型变化的例子。
标签和可选参数
参数的名称可以带一个标签，这样可以通过标签名为其选择参数。
let f ~name1:a ~name2:b = a + b
可以这样调用：
utop # f ~name1:2 ~name2:50;;
- : int = 52
utop # f ~name2:50 ~name1:2;;
- : int = 52
如果标签和参数名一致，可以直接：
let f ~a ~b = a + b
标签参数一般不直接使用，因为需要手动指定每一个标签名，导致比较麻烦。
一般标签函数需要和可选函数搭配使用。
let f ?name1:(a=5) b = a + b
还可以简化为：
let f ?(a=5) b = a + b
调用时可以指定可选参数，如果不指定就是默认值：
utop # f ~a:10 10;;
- : int = 20
utop # f 10 ~a:10;;
- : int = 20
utop # f 10;;
- : int = 15
尾递归
考虑一个求斐波那契数列的函数（不考虑非正数的情况）：
let rec fib n =
if n < 3 then 1
else fib (n - 1) + fib (n - 2)
如果传入的参数很大，比如达到了 40 甚至 50 ，或者更高，就会发现计算速度很慢。这是因为递归的开销很大，需要重复计算。
但是如果是尾递归的函数，就会被编译器优化为循环操作。尾递归函数的意思是函数递归调用时的结果不在栈上暂存。
比如上述 fib 函数可以尾递归化如下：
let fib_tr n =
let rec fib_aux n p q =
if n = 1 then q
else fib_aux (n - 1) q (p + q)
in
fib_aux n 0 1
测试较大参数的时候，结果也是秒出的（参数太大了整数先溢出了）。
这个函数的尾递归化原理较为复杂，下面详细分析一下。
在函数 fib_tr 内部定义一个辅助函数 fib_aux ，该函数的参数 n 仅用作计数，参数 p 表示前一个值，参数 q 表示当前的值。
按照斐波那契数列定义，下一个值是前一个值加上当前的值，于是在递归调用的时候将当前值作为前一个值，将下一个值作为当前值。
当 n 计数到 1 的时候，当前值就是数列的结果了。初值的选取则是根据 n = 1 的情况，选取为 1 ，而前一个值则选为 0 ，确保 n = 2 时相加结果也是 1 。
发表于 2023-11-25 21:40
