1. 语法糖——元组的“名称引用”与“位置引用”:
(e1,...,en) <=> {1=e1,...,n=en}
类型:t1 * … * tn <=> {1:t1,...,n:tn}
2. 自定义数据类型绑定:
datatype mytype = TwoInts of int * int
| Str of string
| Pizza
3. 访问自定义数据类型的值:
fun f x = (* f has type mytype -> int *)
case x of
Pizza => 3
| TwoInts(i1, i2) => i1 + i2
| Strs=>String.sizes
4. 数据类型绑定与Case表达式简化描述:
datatype t = C1 of t1 | C2 of t2 | … | Cn of tn
case e of p1 => e1 | p2 => e2 | … | pn => en
5. 类型别名(Type Synonyms)
type foo = int
6. 自定义列表类型
datatype my_int_list = Empty
| Cons of int * my_int_list
7. 多态类型(Polymorphic Datatypes)
datatype 'a option = NONE | SOME of 'a
二叉树定义:
datatype ('a, 'b) tree = Node of 'a * ('a, 'b) tree * ('a, 'b) tree
| Leaf of 'b
8. Val-Binding的真相——模式匹配(Pattern-Matching for Each-Of Types)
例8-1-1:
fun sum_triple (triple : int * int * int) =
case triple of
(x, y, z) => z + y + x
例8-2-1:
fun full_name (r : {first : string, middle : string, last : string}) =
case r of
{first = x, middle = y, last = z} => x ^ "" ^ y ^ "" ^ z
例8-2-2:
fun full_name (r : {first : string, middle : string, last : string}) =
let val {first = x, middle = y, last = z} = r
in
x ^ "" ^ y ^ "" ^ z
end
例8-1-2:
fun sum_triple (triple : int * int * int) =
let val (x, y, z) = triple
in
x + y + z
end
例8-2-3:
fun full_name {first = x, middle = y, last = z} =
x ^ "" ^ y ^ "" ^ z
例8-1-3:
fun sum_triple (x, y, z) =
x + y + z
9. 题外话——类型推导(Type inference)
In ML,every variable and function has a type (or your program fails to type-check)—
type inference only means you do not need to write down the type.
10. 题外话——多态类型与等价类型
'a list * 'a list -> 'a list
可以替换为:string list * string list -> string list
不能替换为:string list *int list -> string list
'a 必须替换为同样的数据类型
11. 嵌套模式(Nested Patterns)
a::(b::(c::d)) 包含至少3个元素的list
a::(b::(c::[])) 只包含3个元素的list
模式匹配的递归定义(the elegant recursive denition of pattern matching)
1 |
A variable pattern(x) matches any value v and introduces one binding (from x to v). |
2 |
The pattern C matches the value C,if C is a constructor that carries no data. |
3 |
The pattern C p where C is a constructor and p is a pattern matches a value of the form C v (notice the constructors are the same) if p matches v (i.e., the nested pattern matches the carried value). It introduces the bindings that p matching v introduces. |
4 |
The pattern (p1,p2,...,pn) matches a tuple value (v1,v2,...,vn) if p1 matches v1 and p2 matches v2, ..., and pn matches vn. It introduces all the bindings that the recursive matches introduce. |
5 |
(A similar case for record patterns of the form {f1=p1, … , fn=pn} ...) |
例11-1-1:
fun len xs =
case xs of
[] => 0
| x::xs' => 1 + len xs'
例11-1-2:
fun len xs =
case xs of
[] => 0
| _::xs' => 1 + len xs'
通配符(wildcard) (_) 指代任意没有定义数据类型的值
12. 可用的嵌套模式范例:
例12-1:
exception BadTriple
fun zip3 list_triple =
case list_triple of
([], [], []) => []
| (hd1::tl1, hd2::tl2, hd3::tl3) => (hd1, hd2, hd3)::zip3(tl1, tl2, tl3)
| _ => raiseBadTriple
fun unzip3 lst =
case lst of
[] => ([], [], [])
| (a, b, c)::tl => let val (l1, l2, l3) = unzip3 tl
in
(a::l1, b::l2, c::l3)
end
例12-2:
datatype sgn = P | N | Z
fun multsign (x1, x2) =
let fun sign x = if x = 0 then Z else if x > 0 then P else N
in
case(sign x1,sign x2) of
(Z, _) => Z
| (_, Z) => Z
| (P, P) => P
| (N, N) => P
| _ => N (* many say bad style; I am okay with it *)
end
13. 多重选择的函数定义(Multiple Cases in a Function Binding)
例13-1:
datatype exp = Constant of int | Negate of exp | Add of exp * exp | Multiply of exp * exp
fun eval(Constant i) = i
| eval(Negate e2) = ~(eval e2)
| eval(Add(e1, e2)) = (eval e1) + (eval e2)
| eval(Multiply(e1, e2))=(eval e1) * (eval e2)
fun append ([], ys) = ys
| append (x::xs', ys) = x::append(xs', ys)
一般形态(语法糖形式):
fun f p1 = e1
| f p2 = e2
...
| f pn = en
普通写法:
fun f x =
case x of
p1 => e1
| p2 => e2
...
| pn => en
14. 异常(Exception)
输出异常(关键字) raise:raise List.Empty
定义异常(关键字)exception:exception MyUndesirableCondition
15. 尾递归和累加器
fun sum1 xs =
case xs of
[] => 0
| i::xs' => I + sum1 xs'
16. 尾递归的定义
递归的调用出现在尾位置(saying a call is a tail call if it is in tail position.)
尾位置定义:
1 |
In fun f(x) = e, e is in tail position. |
2 |
If an expression is not in tail position, then none of its sub expressions are in tail position. |
3 |
If if e1 then e2 else e3 is in tail position, then e2 and e3 are in tail position (but not e1).(Case-expressions are similar.) |
4 |
If let b1 … bn in e end is in tail position,then e is in tail position (but no expressions in the bindings are). |
5 |
Function-call arguments are not in tail position. |