| この章のキーワード: 局所変数，組，パターンマッチ，再帰関数 |
|
前回，非常に簡単な関数の宣言方法を学んだが，本当に簡単なことしか
実現できないことに気づくだろう．例えば，複数のパラメータをとるような
関数はどのようにすればよいのだろうか．また，関数本体の式が複雑になるにつれ，
その意味を追うのが大変になってくることに気づくかもしれない．
今回の主な内容は，再帰的な関数定義による繰り返しの実現であるが，
その前に少し寄り道をして，一時的に使用する局所変数の宣言と，
複数の値をまとめて扱うためのデータ構造である組(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.9439510233
``let base = '' 以下が let 式である．base という局所変数を宣言，
底面の面積に束縛したあとで，体積を計算している．(その結果は vol_cone
になる．)
一般的な let-式の形は
let x = e1 in e2
で，e1, e2 が let 式であってももちろんよい．
この式は，
-
e1を評価し，
- x をその結果に束縛して，
- e2 の評価
を行い，式全体の値は e2 の評価結果になる．変数 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-宣言は，大域環境の末尾に変数の束縛を表すペア
を追加していくものであった．
これに対し，let x = e1 in e2
の場合，xのエントリが追加される
のはe2の評価をする一時的な間だけである．この追加される期間
が，有効範囲に対応している．
| 変数名 |
値 |
| ⋮ |
⋮ |
| ⋮ |
⋮ |
| 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;;
の let area = c_area 2.0 の実行中の環境は，図3.2の
ように表される．関数本体評価中の環境に注意すること．
| 変数名 |
値 |
| ⋮ |
⋮ |
| ⋮ |
⋮ |
| 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 の実行．二重線以下が一時的に発生した束縛を表す．
Exercise 1 次の各式においてそれぞれの変数の参照がどの定義を指すかを示せ．
また評価結果を，まずコンパイラを使わずに予想せよ．その後で
実際に確かめよ．
-
let x = 1 in let x = 3 in let x = x + 2 in x * x
- let x = 2 and y = 3 in (let y = x and x = y + 2 in x * y) + y
- let x = 2 in let y = 3 in let y = x in let z = y + 2 in x * y * z
Exercise 2 トップレベルでの以下の2種類の宣言の違いは何か？(ヒント:
e2 がxを含む場合を考えよ．)
-
let x = e1 and y =
e2;;
- let x = e1 let y =
e2;;
次に，複数の値をまとめて扱う方法を見ることにする．これによって
複数のパラメータを取る関数，複数の結果を返す関数を定義することができる．
数学では，ベクトルのように，複数の「ものの集まり」から，それぞれの要素を
並べたものを要素とするような，新たな集まり(集合の言葉でいえば(デカルト)積)を定義
することがある．それと同じように 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", 1, 16)
# (* Igarashi was born on January 16 :-) *);;
val igarashi : string * string * int * int = ("Atsushi", "Igarashi", 1, 16)
組の中の値にアクセスするにはパターンマッチ(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 = 1
val f : int = 16
厳密には上のパターンは4つの変数パターンと組パターン
を使って構成される複合的なパターンである．変数パターンは，「i」のよ
うに変数名のみから構成され，「何にでもマッチし，iをマッチした値に束
縛する」ものである．2組パターンは，(⟨ パターン1 ⟩, ...,⟨ パター ンn ⟩)という形でより小さい部分パターンから構成さ
れる．パターンとしての解釈は，「n個の組で，それぞれの要素が
⟨ パターンi ⟩にマッチするとき全体がマッチし，部分パターンが作
る束縛の全体をパターン全体の束縛とする」となる．また，ひとつのパターン
中に変数はただ1度しか現れることができない．例えば，組中のふたつの要素
が等しいことをパターンで表すことはできない．
# (* 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
もうひとつ，よく使うパターンを紹介しよう．
上の例では，全部の要素に名前をつけているが，プログラムの部分によっては一部
の要素だけ取り出せばよい場合もある．このような場合には，変数の代りに， _
(アンダースコア)という 「何にでもマッチするがマッチした内容は捨てる」
ワイルドカードパターン(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要素の和)を同時に返している関数と思う
こともできる．このように，組は，複数の引数を伴う関数だけでなく，複数の
結果を返す関数を模倣するのにも使用される．
Exercise 3 2実数の相乗平均をとる関数 geo_mean を定義せよ．
Exercise 4 2行2列の実数行列と2要素の実数ベクトルの積をとる関数 prodMatVec を定義せよ．
行列・ベクトルを表現する型は任意でよい．
Exercise 5 次のふたつの型
-
float * float * float * float
- (float * float) * (float * float)
の違いを，その型に属する値の
構成法と，要素の取出し方からみて比較せよ．
Exercise 6 let (x : int) = ... などの (x : int) もパターンの一種である．
このパターンの意味をテキストに倣って(何にマッチし，どんな束縛を発生させる
か)説明せよ．
関数定義は再帰的に，つまり定義のなかで自分自身を参照するように，行うことも
可能である．このような再帰関数(recursive function)は，繰り返しを
伴うような計算を表現するために用いることができる．
まずは簡単な例から見ていこう．自然数 n の階乗 n! = 1 � 2 �
⋯ � n を計算する関数を考える．この式を別の見方をすると，
-
階乗が定義される数のうち最も小さい数(つまり 1)の階乗は 1 であり4，
- n! = (n-1)! ⋅ n，つまり n の階乗は n-1 の階乗から
計算できる
ことがわかる．これは，自分自身を使って定義している再帰的な定義である．
ただし，大きな数の階乗はより小さな数の階乗から定義されており，
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)) |
→ |
square(2 * 2) |
| |
→ |
square(4) |
| |
→ |
4 * 4 |
| |
→ |
16 |
次に再帰を伴う評価について見てみよう．fact 4 は，以下のような手順で
評価される．
| fact 4 |
→ |
if 4 = 1 then 1 else fact(4-1) * 4 |
| |
→ |
fact (4 - 1) * 4 |
| |
→ |
fact 3 * 4 |
| |
→ ⋯ → |
(fact (3-1) * 3) * 4 |
| |
→ ⋯ → |
(fact 2 * 3)* 4 |
| |
→ ⋯ → |
((fact (2-1) * 2) * 3) * 4 |
| |
→ ⋯ → |
((fact 1 * 2) * 3) * 4 |
| |
→ ⋯ → |
((1 * 2) * 3) * 4 |
| |
→ ⋯ → |
(2 * 3) * 4 |
| |
→ ⋯ → |
6 |
| |
→ ⋯ → |
24 |
値呼出しは直観的で多くのプログラミング言語で使われているものの，余計な
計算を行ってしまうことがあるという欠点がある．例えば，(やや人工的な例
であるが)
# 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(square(2)) |
→ |
square(2) * square(2) |
| |
→ |
(2 * 2) * square(2) |
| |
→ |
4 * square(2) |
| |
→ |
4 * (2 * 2) |
| |
→ |
4 * 4 |
| |
→ |
16 |
| zero(square(square(2))) |
→ |
0 |
この欠点をなくしたものが，必要呼出し(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 ⟨ 関数名 ⟩;; とすると，その関数に与えられた
引数と結果を呼出された順に表示することができる．
# #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) の評価の様子を示す．
| facti (4, 1) |
→ |
if 4 = 1 then 1 else facti(4 - 1, 4 * 1) |
| |
→ |
facti (3, 4) |
| |
→ |
if 3 = 1 then 4 else facti(3 - 1, 4 * 3) |
| |
→ |
facti (2, 12) |
| |
→ |
if 2 = 1 then 12 else facti(2 - 1, 12 * 2) |
| |
→ |
facti (1, 24) |
| |
→ |
if 1 = 1 then 24 else facti(1 - 1, 24 * 1) |
| |
→ |
24 |
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は以下の漸化式を満たすような数列である．
| F1 |
= |
1 |
| F2 |
= |
1 |
| Fn |
= |
Fn-1 + Fn-2 |
# 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 の互除法
Euclid の互除法は，自然数 m と n (ただし m < n)
の最大公約数は，n � m の剰余と m の最大公約数に
等しい性質を用いて，二整数の最大公約数を求める方法である．
組み合わせ数
n 個のもののなかから m 個のものを選びだす組合わせの場合の数
は，
|
|
�
� |
|
�
� |
= |
| n � ⋯ � (n-m+1) |
|
| m � ⋯ � 1 |
|
|
= |
|
|
= |
�
� |
|
�
� |
+ |
�
� |
|
�
� |
ただし
0 ≤ m ≤ n |
|
最後に，二つ以上の関数がお互いを呼び合う相互再帰(mutual
recursion)をみる．相互再帰関数は，一般的に
let rec f1 ⟨ パターン1 ⟩ = e1
and f2 ⟨ パターン2 ⟩ = e2
⋮
and fn ⟨ パターンn ⟩ = en
という形で定義される．各本体の式 ei には自分自身である
fi だけでなく同時に定義される f1, ...,
fn 全てを呼ぶことができる．
非常に馬鹿馬鹿しい例ではあるが，次の関数 even, odd は
-
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
もう少し，現実的な例として，arctan1 の展開形
を考える．途中までの和を求める関数は，正の項を足す関数と
負の項を足す関数を相互再帰的に定義できる．
# 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
ゆっくりと π/4 に収束して行く．
Exercise 7 x は実数，n は 0 以上の整数として，
xn を計算する関数 pow (x,n) を以下の2種類定義せよ．
-
pow の(再帰)呼出しを n 回伴う定義
- pow の(再帰)呼出しは約 log2 n 回ですむ定義．
(ヒント: x2n = (x2)n である．では，x2n+1 = ?)
Exercise 8 前問の pow の最初の定義を反復的にした powi を定義せよ．
(もちろん引数の数は一つ増える．呼出し方も説明せよ．)
Exercise 9 if 式は Objective Caml の関数で表現することはできない．以下の関数は
それを試みたものである．fact 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;;
????
Exercise 10 fib 4 の値呼出しによる評価ステップをテキストに倣って示せ．
Exercise 11 以下の関数を定義せよ．
-
Euclid の互除法で二整数の最大公約数を求める関数 gcd．
- テキストの再帰的な定義で を求める関数 comb．
- fib_pair を反復的に書き直した fib_iter．
- 与えられた文字列のなかで ASCII コードが最も大きい文字を返す
max_ascii 関数．(文字列から文字を取出す方法は 2.2.5
節を参照のこと．)
Exercise 12 neg を単独で用いる必要がなければ，pos と neg は一つの関数に
まとめることができる．一つにまとめて定義せよ．
- 1
- 最後の「不明だった部分を retrieve
する」というのは耳慣れないかもしれないが，UNIX の egrep コマンドでは，()
でマッチした文字列に番号をつけ同じパターン式の中で \ 1
などとして参照することができる．
- 2
- 実は，今まで使ってきた let x = ... の
x も変数パターンである．つまりlet の等号の左辺は常にパターンを記
述する．
- 3
- が，この定義の場合 pair
が他の場所で使われていないので最初の定義の簡潔さに勝るメリットはないだろう
- 4
- 0 の階乗を 1 と定義するほうが数学では標準的である．
- 5
- 現在の Objective Caml の実装では，関数以外のもので
再帰的に定義できる式があるがここでは扱わない．
- 6
- すでに見
たようにパラメータの置換は環境の仕組みで実現されているが，この節では
より単純かつ直観的な置き換えモデルを使って説明を行う．