Lists
构建：
- 语法（syntax）：
[e1, e2]
- 类型检查（type check）：
-
Lists内所有元素都有相同的类型t，记为：t list
-
特殊：
空Lists：[ ]，t可以是任意类型，ML中记为：‘a list
- 求值规则（evaluation rules）：
- 依次计算表达式e，e1得到va, e2得到vb，结果[va, vb]
使用List：
- 添加元素（syntax）
e1::e2，e1匹配为一个t类型的元素，e2匹配为t类型的Lists
val alist = 1::[2,3,4] alist: [1,2,3,4]
- 内置常用函数（syntax）
以下函数均接受一个Lists参数
null：空List，返回true；非空Lists，返回false
hd：返回一个Lists的第一个元素，若该Lists为空，则抛出一个异常（raise exception）
tl：返回一个Lists的所有尾部元素
val e = [e1, e2,e3,...,en]
#1 e 返回e1
#2 e 返回e2
...
#n e 返回en
val t1 = null e false
val t2 = hd e e1
val t3 = tl e [e2,e3,...,en]
- 遍历Lists：
- 因为Lists有不确定的长度，且在ML中没有类似for的关键字，所以常用方式是对Lists进行迭代（recursive）
- 编写递归函数（recursive function）的一般思考过程
a. 基本情况：例如：空List应该返回什么答案
b. 递归情况：如何根据Lists剩余部分来表达答案
实例
fun sum_list (xs: int list) =
if null xs
then 0
else hd xs + sum_list(tl xs)
fun countdown (x: int) =
if x = 0
then []
else x :: countdown(x-1)
fun append (xs: int list, ys: int list) =
if null xs
then ys
else (hd xs) :: append(tl xs, ys)
fun sum_pair_list (xs: (int * int) list) =
if null xs
then 0
else #1 (hd xs) + #2 (hd xs) + sum_pair_list(tl xs)
fun firsts (xs: (int * int) list) =
if null xs
then []
else (#1 (hd xs)) :: (firsts(tl xs))
fun seconds (xs: (int * int) list) =
if null xs
then []
else (#2 (hd xs)) :: (seconds(tl xs))
fun sum_pair_list2 (xs: (int * int) list) =
(sum_list(firsts xs)) + (sum_list(seconds xs))
