• 局所変数とlet式
• 構造のためのデータ型: 組
• 再帰関数

# let vol_cone = (* 半径 2 高さ 5 の円錐の体積 *)
#   let base = pi *. 2.0 *. 2.0 in
#   base *. 5.0 /. 3.0;;
val vol_cone : float = 20.9439510233

let x = e1 in e2

1. e₁を評価し，
2. x をその結果に束縛して，
3. e₂ の評価

# base;;
 base;;
 ^^^^
Unbound value base

# let cone_of_heightTwo r =
#   let base = r *. r *. pi in
#   base *. 2.0 /. 3.0;;
val cone_of_heightTwo : float -> float = <fun>
# let f x =                    (* f(x) = x^3 + (x^3 + 1) *)
#   let x3 = x * x * x in
#   let x3_1 = x3 + 1 in
#   x3 + x3_1;;
val f : int -> int = <fun>
# let g x =                    (* g(x) = x^3 + (x+1)^3 *)
#   let power3 x = x * x * x in
#   (power3 x) * (power3 (x + 1));;
val g : int -> int = <fun>

複数の変数宣言

# let x = 2 and y = 1;;
val x : int = 2
val y : int = 1
# (* swap x and y; 
#    the use of x is bound to the previous declaration! *)
# let x = y and y = x;;
val x : int = 1
val y : int = 2
# let z =
#   let x = "foo" 
#   and y = 3.1 in 
#   x ^ (string_of_float y);;
val z : string = "foo3.1"

let-式，関数呼出しと環境

---

変数名 値 ⋮ ⋮ ⋮ ⋮ sin 正弦関数 max_int 1073741823 ⋮ ⋮	変数名 値 ⋮ ⋮ ⋮ ⋮ sin 正弦関数 max_int 1073741823 ⋮ ⋮ x 5	変数名 値 ⋮ ⋮ ⋮ ⋮ sin 正弦関数 max_int 1073741823 ⋮ ⋮
3+2 の評価中の環境	x+7 の評価中の環境	加算(5+7)実行後の環境

Figure 3.1: 式 let x = 3 + 2 in x + 7 の実行．二重線以下が一時的に発生した束縛を表す．

---

let pi = 3.1415926535;;
let c_area(r) = r *. r *. pi;;
let pi = 1;;
let area = c_area 2.0;;

---

変数名 値 ⋮ ⋮ ⋮ ⋮ pi 3.1415926535 c_area <fun> pi 1	変数名 値 ⋮ ⋮ ⋮ ⋮ pi 3.1415926535 r 2.0	変数名 値 ⋮ ⋮ ⋮ ⋮ pi 3.1415926535 c_area <fun> pi 1 area 12.566370614
c_area 2.0 呼出し直前の環境	関数呼出し直後の環境	実行終了後の環境

Figure 3.2: 式 let area = c_area 2.0 の実行．二重線以下が一時的に発生した束縛を表す．

---

# (1.0, 2.0);;
- : float * float = (1., 2.)

# let bigtuple = (1, true, "Objective Caml", 4.0);;
val bigtuple : int * bool * string * float = (1, true, "Objective Caml", 4.)
# let igarashi = ("Atsushi", "Igarashi", 1, 16)
#         (* Igarashi was born on January 16 :-) *);;
val igarashi : string * string * int * int = ("Atsushi", "Igarashi", 1, 16)

1. データの部分的な構造を記述した式(パターン)と，
2. 与えられたデータの構造と比べることで，
3. パターン記述時には不明だった部分を簡単に知る・使う

# let (i, b, s, f) = bigtuple;;
val i : int = 1
val b : bool = true
val s : string = "Objective Caml"
val f : float = 4.

# let (i, b, s, f) = igarashi;;
val i : string = "Atsushi"
val b : string = "Igarashi"
val s : int = 1
val f : int = 16

# (* matching against a person whose first and family names are the same *)
# let (s, s, m, d) = igarashi;;
 let (s, s, m, d) = igarashi;;
 ^
This variable is bound several times in this matching

# let (i, _, s, _) = bigtuple;;
val i : int = 1
val s : string = "Objective Caml"

# let average (x, y) = (x +. y) /. 2.0;;
val average : float * float -> float = <fun>

# average (5.7, -2.1);;
- : float = 1.8

# let pair = (0.34, 1.2);;
val pair : float * float = (0.34, 1.2)
# average pair;;
- : float = 0.77

# let average pair =
#   let (x, y) = pair in (x +. y) /. 2.0;;
val average : float * float -> float = <fun>

# let add_vec ((x1, y1), (x2, y2)) = (x1 +. x2, y1 +. y2);;
val add_vec : (float * float) * (float * float) -> float * float = <fun>

# add_vec ((1.0, 2.0), (3.0, 4.0));;
- : float * float = (4., 6.)
# let (x, y) = add_vec (pair, (-2.0, 1.0));;
val x : float = -1.66
val y : float = 2.2

• 階乗が定義される数のうち最も小さい数(つまり 1)の階乗は 1 であり⁴，
• n! = (n-1)! ⋅ n，つまり n の階乗は n-1 の階乗から 計算できる

# let rec fact n = (* factorial of positive n *)
#   if n = 1 then 1 else fact (n-1) * n;;
val fact : int -> int = <fun>

# fact 4;;
- : int = 24

# let rec x = x * x + 1;;
 let rec x = x * x + 1;;
 ^^^^^^^^^
This kind of expression is not allowed as right-hand side of `let rec'

• 最小の引数の場合の定義
• ``より小さい''引数における値からの計算式

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

# let zero (x : int) = 0;;
val zero : int -> int = <fun>

#trace ディレクティブ

# #trace fact;;
fact is now traced.
# fact 4;;
fact <-- 4
fact <-- 3
fact <-- 2
fact <-- 1
fact --> 1
fact --> 2
fact --> 6
fact --> 24
- : int = 24

# #untrace fact;;
fact is no longer traced.
# fact 5;;
- : int = 120

# let rec facti (n, res) = (* iterative version of fact *)
#   if n = 1 then res (* equal to res * 1 *) 
#   else facti (n - 1, n * res);;
val facti : int * int -> int = <fun>

# facti (4, 1);;
- : int = 24

# let fact n = (* facti is localized *)
#   let rec facti (n, res) = 
#     if n = 1 then res else facti (n - 1, res * n) 
#   in facti (n, 1);;
val fact : int -> int = <fun>

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

フィボナッチ数

# let rec fib n = (* nth Fibonacci number *)
#   if n = 1 || n = 2 then 1 else fib(n - 1) + fib(n - 2);;
val fib : int -> int = <fun>

# let rec fib_pair n = 
#   if n = 1 then (0, 1)
#   else 
#     let (prev, curr) = fib_pair (n - 1) in (curr, curr + prev);;
val fib_pair : int -> int * int = <fun>

Euclid の互除法

組み合わせ数

let rec f1 ⟨ パターン1 ⟩ = e1
and f2 ⟨ パターン2 ⟩ = e2
  ⋮
and fn ⟨ パターンn ⟩ = en

• 0 は偶数であり，奇数ではない．
• 1 は奇数である，偶数ではない．
• n-1 が偶数なら n は奇数である．
• n-1 が奇数なら n は偶数である．

# let rec even n = (* works for positive integers *)
#   if n = 0 then true else
#   if n = 1 then false else odd(n - 1)
# and odd n = 
#   if n = 0 then false else
#   if n = 1 then true else even(n - 1);;
val even : int -> bool = <fun>
val odd : int -> bool = <fun>
# even 6;;
- : bool = true
# odd 14;;
- : bool = false

# let rec pos n = 
#   neg (n-1) +. 1.0 /. (float_of_int (4 * n + 1))
# and neg n = 
#   if n < 0 then 0.0
#   else pos n -. 1.0 /. (float_of_int (4 * n + 3));;
val pos : int -> float = <fun>
val neg : int -> float = <fun>
# 4.0 *. pos 200;;
- : float = 3.1440864153
# 4.0 *. pos 800;;
- : float = 3.14221726315

# let cond (b, e1, e2) : int = if b then e1 else e2;;
val cond : bool * int * int -> int = <fun>
# let rec fact n = cond ((n = 1), 1, n * fact (n-1));;
val fact : int -> int = <fun>

# fact 4;;
????

1

最後の「不明だった部分を retrieve する」というのは耳慣れないかもしれないが，UNIX の egrep コマンドでは，() でマッチした文字列に番号をつけ同じパターン式の中で \ 1 などとして参照することができる．

2

実は，今まで使ってきた let x = ... の x も変数パターンである．つまりlet の等号の左辺は常にパターンを記 述する．

3

が，この定義の場合 pair が他の場所で使われていないので最初の定義の簡潔さに勝るメリットはないだろう

4

0 の階乗を 1 と定義するほうが数学では標準的である．

5

現在の Objective Caml の実装では，関数以外のもので 再帰的に定義できる式があるがここでは扱わない．

6

すでに見 たようにパラメータの置換は環境の仕組みで実現されているが，この節では より単純かつ直観的な置き換えモデルを使って説明を行う．