前回，非常に簡単な関数の宣言方法を学んだが，本当に簡単なことしか 実現できないことに気づくだろう．例えば，複数のパラメータを持つような 関数はどのようにすればよいのだろうか．また，関数本体の式が複雑になるにつれ， その意味を追うのが大変になってくることに気づくかもしれない．
今回の主な内容は，再帰的な関数定義であるが， その前に少し寄り道をして，計算中に一時的に使用する変数である局所変数(local variable)の宣言と，複数の値をまとめて扱うためのデータ 構造である組(tuple)をみていく．
関数の本体内で，計算が数ステップに及び式が複雑になってくると 部分式の意味を捕らえることが徐々に困難になってくる．
Objective Camlではlet式(宣言ではない)によって，局所変数を宣言し， 値に一時的な名前をつけることができる．
まずは，簡単な例から見ていこう．
# let vol_cone = (* 半径 2 高さ 5 の円錐の体積 *)
let base = pi *. 2.0 *. 2.0 in
base *. 5.0 /. 3.0;;
val vol_cone : float = 20.9439510233333337
“let base = ” 以下が let 式である．base という局所変数を宣言， 底面の面積に束縛したあとで，体積を計算している．(その結果は vol_cone になる．)
一般的な let式の形は
let x = e1 in e2
で，e1, e2 が let 式であってももちろんよい． この式は，
という手順で値が求まる． 変数 x の有効範囲は e2 である． よって vol_cone の宣言以降では base は参照できない．
# base;; base;; ^^^^ Unbound value base
また，e1 はxの有効範囲に含まれない．
もちろん，let式は関数の本体に用いることもできる．また，let式で 局所的に使う補助的な関数を宣言することもできる．3番目の例は，その(やや人工 的な)例である．
# 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式のもっとも素朴な意義は，部分式に名前をつけることによる抽象化の 手段を提供することである．また二次的ではあるが，同じ部分式が 複数回出現する場合にその評価を1度ですませられる，といった効果が得られる． また，部分式の計算方法が似ている場合には，パラメータ抽象を使って， 局所関数を定義することで，プログラムの見通しがよくなる．
let 宣言/式ともに，and キーワードを使って， 複数の変数を同時に宣言することができる．
# 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宣言は，大域環境の末尾に変数の束縛を表すペア を追加していくものであった． これに対し，let x = e1 in e2 の場合，xのエントリが追加される のはe2の評価をする一時的な間だけである．この追加される期間 が，有効範囲に対応している．
また関数呼出しの実行もこれと似ていて，パラメータを実引数に 束縛して本体の実行を行う．ただし，有効範囲は静的に決まるため， 関数が定義された時点での環境を用いて本体を評価する．
let pi = 3.1415926535;; let c_area(r) = r *. r *. pi;; let pi = 1;; let area = c_area 2.0;;
の let area = c_area 2.0 の実行中の環境は，図3.2の ように表される．関数本体評価中の環境に注意すること．
次に，複数の値をまとめて扱う方法を見ることにする．これによって 複数のパラメータを取る関数，複数の結果を返す関数を定義することができる．
数学では，ベクトルのように，複数の「ものの集まり」から，それぞれの要素を 並べたものを要素とするような，新たな集まり(集合の言葉でいえば(デカルト)積)を定義 することがある．それと同じように Objective Caml でも複数の値を並べて，新しいひとつの値を作る ことができる．このような値を組(tuple)と呼ぶ．tuple は，() 内に，式を , で区切って並べて表記する．
# (1.0, 2.0);; - : float * float = (1., 2.)
結果の型 float * float はこの値が，「第1要素 (1.0) が float で， 第2要素(2.0)も float であるような組」であることを示す．* は組の型構築子 である．
組として並べられる要素は二つ以上(メモリの許す限り)いくつでも よく，また同じ型の式でなくてもよい．また，もちろん他の値と同様に let で名前 をつけることができる．
# let bigtuple = (1, true, "Objective Caml", 4.0);;
val bigtuple : int * bool * string * float = (1, true, "Objective Caml", 4.)
# let igarashi = ("Atsushi", "Igarashi", 10, 142)
(* Igarashi's office is at room #142 in 10th build. :-) *);;
val igarashi : string * string * int * int = ("Atsushi", "Igarashi", 10, 142)
組の中の値にアクセスするにはパターンマッチ(pattern matching) の機能を使う．パターンマッチの概念は UNIX の grep などのコマンドでもみられる が，おおざっぱには
ための機能であるとしてよいだろう1． 例えば，(x, y, z, w)というパターンは，4要素からなる組にマッチし， x を第1要素に, y を第2要素に, z を第3要素に， w を第4要素にそれぞれ束縛するパターンである． パターンは変数の束縛(let, 関数のパラメータ)を するところに使用できる．先ほどの，bigtuple の要素は，
# 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 = 10 val f : int = 142
厳密には上のパターンは4つの変数パターンと組パターン を使って構成される複合的なパターンである．変数パターンは，「i」のよ うに変数名のみから構成され，「何にでもマッチし，iをマッチした値に束 縛する」ものである．2組パターンは，(⟨ パターン1 ⟩, …,⟨ パター ンn ⟩)という形でより小さい部分パターンから構成さ れる．パターンとしての解釈は，「n個の組で，それぞれの要素が ⟨ パターンi ⟩にマッチするとき全体がマッチし，部分パターンが作 る束縛の全体をパターン全体の束縛とする」となる．また，ひとつのパターン 中に変数はただ1度しか現れることができない．例えば，組中のふたつの要素 が等しいことをパターンで表すことはできない．
# (* matching against a person whose first and family names are the same *) let (s, s, b, r) = igarashi;; let (s, s, b, r) = igarashi;; ^ This variable is bound several times in this matching
もうひとつ，よく使うパターンを紹介しよう． 上の例では，全部の要素に名前をつけているが，プログラムの部分によっては一部 の要素だけ取り出せばよい場合もある．このような場合には，変数の代りに， _ (アンダースコア)という 「何にでもマッチするがマッチした内容は捨てる」 ワイルドカードパターン(wildcard pattern)と呼ぶパターンを使用することができる．
# let (i, _, s, _) = bigtuple;; val i : int = 1 val s : string = "Objective Caml"
次に，float のペア(2要素の組)から各要素の平均をとる関数を定義してみ よう．パラメータを今までのように変数とする代りに組パターンを用いて，
# let average (x, y) = (x +. y) /. 2.0;; val average : float * float -> float = <fun>
と宣言することができる．average の型 float * float -> float は 「実数のペア float * float を受け取り，実数を返す」ことを示している． (型構築子 * の方が -> より強く結合するので，この型は (float * float) -> float と同じ意味である．)これを使って，ふたつの実数の平均は
# average (5.7, -2.1);; - : float = 1.8
として求められる． このように，組は，引数が複数あるような 関数を模倣するためによく用いられる．ここで，わざわざ「模倣」と書いたのは， 実際には average は組を引数としてとる1引数関数であるからである． また，実は Objective Caml の関数はすべて1引数関数である．つまり，average は
# 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>
と定義することもできる3．
組の要素として組を使うこともできる．次の定義は，(2次元)ベクトルの加算 をするものである．
# 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要素の和，と第2要素の和)を同時に返している関数と思う こともできる．このように，組は，複数の引数を伴う関数だけでなく，複数の 結果を返す関数を模倣するのにも使用される．
関数定義は再帰的に，つまり定義のなかで自分自身を参照するように，行うことも 可能である．このような再帰関数(recursive function)は，繰り返しを 伴うような計算を表現するために用いることができる．
まずは簡単な例から見ていこう．自然数 n の階乗 n! = 1 � 2 � ⋯ � n を計算する関数を考える．この式を別の見方をすると，
ことがわかる．これは，自分自身を使って定義している再帰的な定義である． ただし，大きな数の階乗はより小さな数の階乗から定義されており， 1 に関しては，自分自身に言及することなく定義されている．これは 再帰定義が意味をなすための，非常に重要なポイントである． この規則を Objective Caml で定義すると，
# let rec fact n = (* factorial of positive n *)
if n = 1 then 1 else fact (n-1) * n;;
val fact : int -> int = <fun>
となる．(n-1に括弧が必要なことに注意．) 関数本体中に fact が出現していることがわかるだろう． また，上で述べた規則が素直にプログラムされていることがわかる． この fact は正の整数に対しては，正しい答えを返す．
# fact 4;; - : int = 24
一般には，再帰関数を定義する際にはキーワード rec を let の後につけなければならないこと以外，文法は普通の関数定義と 同じである．また，rec が有効なのは関数宣言のみである5．
# 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'
はエラーである(そもそも「定義」といえない．また，x に関する二次方程式 x = x2 −1 を解いてくれるわけでもない．)
再帰関数を定義する際には，この階乗の例のように，何らかの意味で 引数が減少していくことが重要であり，実際の関数定義は
とを場合わけを使って組み合わせることからなる．一般的なアドバイスとして， 再帰関数を定義するときには「どうやって計算するか」よりも 「この関数は何を計算するのか」ということを，まずはっきり させることが重要である．
さて，これまでに，式は値に評価されること，関数適用式 は，パラメータを実引数で置き換えたような式を評価する6，ということ は学んだが，square(square(2)) のような式の，二つある関数適用のうち， どちらを先に評価するか，といった「どのような順番で」値に評価されるか については説明してこなかった． そのひとつの理由は， 再帰関数を導入するまでにふれた式については，評価方法に関わらず 値が変らなかったからである． このような部分式の評価順序を評価戦略(evaluation strategy)という． ここですこし寄り道をして，いろいろな評価戦略をみていこう．
最も単純かつ人間が紙の上で計算する場合と近いのが， 「関数を適用するときにはまず引数を値に評価する」という 値呼出し(call-by-value)の戦略である． 例えば，上の式は square の定義を
# let square x = x * x;; val square : int -> int = <fun>
とすると，
|
というように，まず，外側の square の引数である square(2) の評価を 行っている．Objective Caml を含む多くのプログラミング言語では，値呼出しが使われてい る．
次に再帰を伴う評価について見てみよう．fact 4 は，以下のような手順で 評価される．
|
値呼出しは直観的で多くのプログラミング言語で使われているものの，余計な 計算を行ってしまうことがあるという欠点がある．例えば，(やや人工的な例 であるが)
# let zero (x : int) = 0;; val zero : int -> int = <fun>
のような関数は，引数がどんな整数であろうとも，0を返すにも関わらず， zero(square(square(2))) のような式の評価の際，引数を計算してしまう． また，値呼び出しの言語では，条件分岐を関数で表現することはできない(練 習問題参照)．
この欠点は，とにかく引数を先に評価していくこと(この性質を eagerness, strictness と呼ぶことがある)に起因する．これに対して，いまから述べる ふたつの戦略は，lazy な評価と呼ばれ，「引数は使うまで評価しない」戦略である．
まず，lazy な戦略のひとつめが，「外側の関数適用から，引数を式のままパラメー タに置換する」名前呼出し(call-by-name)である．この戦略の下では， 先ほどの square(square(2)) および，zero(square(square(2))) は，それぞれ，
|
のように評価される．たしかに引数を使わない関数の評価においては無駄が なくなっていることがわかる．その代わりに，計算式をそのままコピーしてしまう ために，部分式 square(2) の計算が二度発生している．
この欠点をなくしたものが，必要呼出し(call-by-need)の戦略であ る．これは，「外側の関数適用から，引数を式のままパラメー タに置換するが，一度評価した式は，結果を覚えておいて二度評価しない」もので， パラメータを引数で置換する代りに，引数式の共有関係を示したよう なグラフで考えるとわかりやすい．
| square(square(2)) | ��→�� |
* /^/[d] /_/[d] square(2) | ��→�� |
* /^/[d] /_/[d] * /^/[d] /_/[d] 2 | ��→�� |
* /^/[d] /_/[d] 4 | ��→�� | 16 |
call-by-need で評価が行われる言語には Haskell, Miranda などがあり，い ずれも関数型言語である．lazy な言語には無限の大きさを持つ構造などをき れいに表現できるなどの利点があるが，部分式がいつ評価されるかわかりにく いため，入出力などとの相性が悪い．また実装も call-by-value 言語に比べ 複雑である．(上に示したようなグラフの書き換えに相当する graph reduction という技術がよく用いられている．)
ここでプログラムのデバグに便利なディレクティブを紹介しておこう． #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 ディレクティブで以降の表示をやめることができる．
# #untrace fact;; fact is no longer traced. # fact 5;; - : int = 120
上で定義した fact 関数の評価の様子をみるとわかるように， 計算途中で「関数呼び出し後に，あとで計算される部分」 ((...) * 3) * 4 といったものを何らかの形で記憶して おかなければならない．n が大きくなると この式の大きさも大きくなり，評価に必要な空間使用量が大きく なってしまう．ところが乗算に関しては結合則から， ((n−2)! � (n−1)) � n) = (n−2)! � ((n−1) � n) が成立するため (n−2)! の計算にとりかかる前に，n � (n−1) を先に 計算してしまうことで，「あとで計算する部分」の大きさを小さく保つことが 可能である． このような工夫をプログラムすることを考えると，引数 n の情報以外に， 「本来なら残りの計算である式の結果」の情報が必要であり，
# 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>
のような定義になる．引数 res が，fact の実行過程における 再帰呼出しの外側の乗算式の値に対応する．この関数は， 正確には，facti (n,m) で，n! � m を計算する．
# facti (4, 1);; - : int = 24
以下に，facti (4, 1) の評価の様子を示す．
|
fact 4 と違い，計算の途中経過の式が小さい(引数の大きさに依存しない)ことが わかるだろう．また，どの段階においても facti の引数 n, m に関して，
| n!��m�=�120�=�4! |
が成立している．このような定義を，再帰呼出しが本体中の計算の一番最後に あることから，末尾再帰的(tail-recursive)である，という．一 般には再帰関数は再帰が深くなるにつれ，メモリの使用量が増大するが，賢い コンパイラは末尾再帰関数を(自動的に)特別扱いして，メモリの使用量が再帰 の深さに関わらず固定量であるようなコードを生成することができる．また， この関数定義は C 言語などで行なう for 文などの繰り返し構文を使ったプ ログラムに似ているため，反復的(iterative)な定義ということも ある．どんな再帰関数も反復的に定義すればよいというわけでもない．実際， 素朴な再帰的定義を反復的にすると引数の数がひとつ増え，それに伴って定義 のわかりやすさがかなり減少する．また，(慣れれば) fact から facti の定義を導くのはほぼ機械的なのだが，より複雑な(具体的には 再帰呼び出しが複数回発生するような)再帰関数では，単純に反復的な 定義に変換することはできない．
ところで，ここでは facti をトップレベルの関数として宣言したが， これはいわば補助的な関数である．第1引数を1以外 でよぶ必要がない場合は，facti を誤用されないように，
# 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>
同じ名前の関数を宣言することで隠すのが，Objective Camlプログラミングの常套 テクニックとして使われる．
これまでに登場した再帰関数は再帰呼出しを行う場所がせいぜい1個所しかなかった． このような再帰の仕方を線形再帰と呼ぶことがある．ここでは再帰呼出しが 2個所以上で行われるような再帰関数をいくつかみていく．
フィボナッチ数列 Fiは以下の漸化式を満たすような数列である．
|
n 番目のフィボナッチ数を求める関数は，
# 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>
として宣言できる．else節に再帰呼出しが2個所現れている．
しかし，この定義は，Fn の計算にFn−2の計算が 二度発生するなど，非常に多くの再帰呼出しを伴うために効率的ではない． (fib 30 の評価を試してみよ．)これを改善したのが，次の定義である．
# 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>
この定義では，n から Fn とともに Fn−1 も 計算する．また，線形再帰的定義になっている．
Euclid の互除法は，自然数 m と n (ただし m < n) の最大公約数は，n � m の剰余と m の最大公約数に 等しい性質を用いて，二整数の最大公約数を求める方法である．
n 個のもののなかから m 個のものを選びだす組合わせの場合の数 (
| n� |
| m� |
) は，
| ⎛ ⎜ ⎝ |
| ⎞ ⎟ ⎠ | =�� |
|
で定義される．これを再帰的に
|
と定義することもできる．
最後に，二つ以上の関数がお互いを呼び合う相互再帰(mutual recursion)をみる．相互再帰関数は，一般的に
let rec f1 ⟨ パターン1 ⟩ = e1 and f2 ⟨ パターン2 ⟩ = e2 ⋮ and fn ⟨ パターンn ⟩ = en
という形で定義される．各本体の式 ei には自分自身である fi だけでなく同時に定義される f1, …, fn 全てを呼ぶことができる．
非常に馬鹿馬鹿しい例ではあるが，次の関数 even, odd は
という再帰的な定義に基づき，与えられた正の整数が偶数か奇数か判定する関数で ある．
# let rec even n = (* works for positive integers *)
if n = 0 then true else odd(n - 1)
and odd n =
if n = 0 then false else even(n - 1);;
val even : int -> bool = <fun>
val odd : int -> bool = <fun>
# even 6;;
- : bool = true
# odd 14;;
- : bool = false
もう少し，現実的な例として，arctan1 の展開形
| �=�1�−� |
| �+� |
| �−� |
| �⋯ +� |
| �−� |
| �⋯ |
を考える．途中までの和を求める関数は，正の項を足す関数と 負の項を足す関数を相互再帰的に定義できる．
# 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.14408641529876087
# 4.0 *. pos 800;;
- : float = 3.14221726314786043
ゆっくりと π/4 に収束して行く(誤差があるので 実際にはちょっと違う値に収束してしまうが)．
# 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;; ????
| n� |
| m |