Functions

函数

(* 非递归函数定义 *)
let func x = ...

(* 递归函数定义：多了一个 rec *)
let rec func x = ...

Mutually Recursive Function

很类似于数学里的螺旋归纳法。用 and 关键词定义

1 2	let rec f x1 ... xn = e1 and g y1 ... yn = e2

匿名函数

1
2
3

let inc x = x + 1
(* 等价形式 *)
let inc = fun x -> x + 1

函数：多态

其实更类似于模板自动推导？

1	let first x y = x

参数的名字

(* 参数名字，[name] 是用于给别人看的，[arg] 是在函数内部使用的  *)
let function ~name1:arg1 ~name2:arg2 = ...

(* 参数带类型 *)
let function ~name1:(default1: int) ~name2:(default2: int) = ...

(* 可选参数带默认值 *)
let function ?name:(arg1 = default_value_1) =

Essence of Function

Function

每一个 function 其实都只接受一个参数

let f x1 x2 ... xn = e

(* 等价于 *)
let f =
    fun x1 ->
        (fun x2 ->
            (...
                (fun xn -> e)...))

从 type 上也可看出端倪

1 2	t1 -> t2 -> t3 -> t4 t1 -> (t2 -> (t3 -> t4))

所以 function type 是 right-associative 的，但是 function application 是 left associative 的

1 2	f x1 x2 ... xn (((f x1) x2 ) ...) xn

尾递归优化

一般函数的递归调用会占用栈空间 $O(d)$ ，所以递归深度有限制。通过尾递归优化，可以把 $O(d)$ 优化到 $O(1)$ .

尾递归优化的写法：在 function return 的时候，把要 return 的值放在参数里，而不是当成返回值，答案即是递归结束时的参数值。

The “remaining computation” —the addition of 1— now happens before the recursive call not after.

let rec count n = 
    if n = 0 then 0 else 1 + count (n-1)

(* 尾递归优化 *)
let rec count_aux n accumulate = 
    if n = 0 then acc else count_aux (n - 1) (accumulate + 1)

let count n = count_aux n 0 (* 包装，将 accumulate 参数隐藏 *)