この章のキーワード: 高階関数，多相性，多相的関数，型推論
Objective Caml を始めとする関数型言語では，関数を整数・文字列などのデータと
同じように扱うことができる．すなわち，ある関数を，
他の関数への引数として渡したり，組などのデータ構造に
格納したりすることができる．このことを「Objective Caml では関数は第一級の値(first-class value)である」といい，また関数を引数/返り値とする
ような関数を高階関数(higher-order function)と呼ぶ．
4.1.1 関数を引数とする関数
まず，前章の復習をかねて，12 + 2 2 + ⋯ + n2 を計算する
関数 sqsum と，13 + 2 3 + ⋯ + n3 を計算する
関数 cbsum を定義してみよう．
# let rec sqsum n =
# if n = 0 then 0 else n * n + sqsum (n - 1)
# let rec cbsum n =
# if n = 0 then 0 else n * n * n + cbsum (n - 1);;
val sqsum : int -> int = <fun>
val cbsum : int -> int = <fun>
よく観察するまでもなく，この二つの関数の定義は酷似していることが
わかるだろう．プログラミングの重要な作業の一つは，
類似の計算手順を関数によって共有することである．
この二つの関数の共通部分を吸収するような関数を定義できないだろうか．
このふたつの関数の似ている点は，(1) n が 0 ならば 0 を返すこと，
(2)再帰呼出しの結果と n に関する計算結果の和がとられていること，の二
点で，違いは n に関する計算手順だけである．この「計算手順」という差
異をパラメータとして表現するにはどうすればよいだろうか？もともと計算手
順を抽象化したものが関数であるので，「関数をパラメータとする関数」を定
義すればよさそうである．それを素直に表現したのが以下の定義である．
# let rec sigma (f, n) =
# if n = 0 then 0 else f n + sigma (f, n-1);;
val sigma : (int -> int) * int -> int = <fun>
この関数 sigma は型が示しているように，整数上の関数 f と整数 n の組を
受け取って，整数を返す．(型の読み方: 型構築子 * と -> は * の方が優先
度が高い．) これを使って，sqsum と cbsum は，
# let square x = x * x
# let sqsum n = sigma (square, n)
# let cbsum n =
# let cube x = x * x * x in sigma (cube, n);;
val square : int -> int = <fun>
val sqsum : int -> int = <fun>
val cbsum : int -> int = <fun>
と定義することができる．高階関数に渡すだけの補助的な関数は，
他で必要ない場合は，cbsum の例のように let-式で局所束縛を
行うか，次節で説明する匿名関数を使うのがよいだろう．
# sqsum 5;;
- : int = 55
# cbsum 5;;
- : int = 225
さて，関数 sigma は，Σi=0n f(i) のような計
算を異なる f について行いたい場合に便利である．しかし，これまでに
みた関数は let を用いて定義するしかなく，具体的な関数 f ひとつひ
とつについて，新しい名前をつけて定義をしなければならない，というやや面
倒な手順1を踏まな
ければならない．
関数型言語では，名前のない関数，匿名関数(anonymous function)
を扱う手段がたいてい用意されていて，Objective Caml もその例外ではない．Objective Caml では
匿名関数は
fun ⟨ パターン ⟩ -> e
という形をとり，⟨ パターン ⟩で表される引数を受け取り式 e
を計算する．この「fun 式」は関数が必要な場所どこにでも使用することができる．
# let cbsum n = sigma ((fun x -> x * x * x), n);;
val cbsum : int -> int = <fun>
# let sq5 = ((fun x -> x * x), 5) in
# sigma sq5;;
- : int = 55
# (fun x -> x * x) 7;;
- : int = 49
2,3番目の例のように，匿名関数は組の要素にもなり，また(あまり実用的な
意味はないが)直接適用することもできる．
また，いずれの例でも fun のまわりの () が必要である(これがないと，
“, n” が関数本体の一部と思われてしまい，x * x * x と n の
組を返す関数として解釈されてしまう．一般的には，fun はできる限り先まで
関数本体と思い込もうとするので，適宜()を使ってどこまで関数本体か
示してやる必要がある．)
実は，let による関数宣言
let f x = e
は
let f = fun x -> e
の略記法である．このことから，関数を構成すること (fun)と，
それに名前をつけること (let) は，必ずしも関連していない別の仕組みで
あることがわかる．
4.1.3 カリー化と関数を返す関数
Objective Caml の関数は全て一引数であるため，引数が二つ以上必要な関数を定義す
るには組を用いることをみてきた．ここでは，「関数を返す関数」を使って引
数が複数ある関数を模倣できる方法をみる．このような「関数を返す関数」を
有名な論理学者Haskell Curry の名をとってカリー化関数(curried
function)と呼ぶ2．
基本的なアイデアは「x と y を受け取り e を計算する関数」を「
x を受け取ると，『y を受け取って e を計算する関数』を返す
関数」として表現することである．具体的な例として，二つの文字列 s1,
s2 から s1s2 のような連結をした文字列を返す関数を考えてみよう．
これまでにみてきた，組を使った定義では，
# let concat (s1, s2) = s1 ^ s2 ;;
val concat : string * string -> string = <fun>
と定義され，型はまさに「文字列を二つ(組にして)受け取り文字列を返す」
ことを表している．使う場合も二つの文字列を同時に指定して
concat ("abc", "def") のように呼び出す．
さて，この関数を カリー化関数として定義してみよう．
# let concat_curry s1 = fun s2 -> s1 ^ s2;;
val concat_curry : string -> string -> string = <fun>
concat_curry は fun 式を用いて，「s2 を受け取って(既に受け取り済の)
s1 と連結するような関数」を返している．concat_curry の型は
string -> (string -> string) と同じで，そのことを示している．
この関数を呼び出すには，2回の関数適用を経て，
# (concat_curry "abc") "def";;
- : string = "abcdef"
のように行う．(...) 内の関数適用で，「"abc" と与えられた引数を
連結するような関数」が返ってきており，外側の関数適用 (...) "def"
で文字列の連結が行われる．
カリー化関数は，組を用いた定義と違って，最初のいくつかのの引数を
固定したような関数を作りたい時に簡潔に実現できる．例えば，敬称 Mr. を
名前(文字列)に付加する関数を
# let add_title = concat_curry "Mr. ";;
val add_title : string -> string = <fun>
# add_title "Igarashi";;
- : string = "Mr. Igarashi"
と定義することができる．add_title は引数の置き換えモデルにした
がって，fun s2 -> "Mr. " ^ s2 という関数に束縛されている
と考えることができる．
このように，カリー化された関数の一部の引数を与えて，特化した
関数を作ることを部分適用(partial application)と呼ぶ．
カリー化関数の型は，読み方によって，「二引数の関数の型」と読むことも，
「関数を返す関数」と読むこともできる．
関数定義の文法拡張
上のカリー化関数の定義方法を，fun を入れ子にすることによって，
三引数，四引数の関数の表現に拡張していくことも可能である．
実は，Objective Caml では，fun を入れ子にする代りに，let や fun でのパラ
メータパターンを複数個並べることによって，カリー化関数をより簡潔に定義
することができる．先の例は，
# let concat_curry s1 s2 = s1 ^ s2;;
val concat_curry : string -> string -> string = <fun>
と定義することも，
# let concat_curry = fun s1 s2 -> s1 ^ s2;;
val concat_curry : string -> string -> string = <fun>
と定義することも可能である．一般的には，
fun ⟨ パターン1 ⟩ -> fun ⟨ パターン2 ⟩ -> ... fun ⟨ パターンn ⟩ -> e
は
fun ⟨ パターン1 ⟩ ⟨ パターン2 ⟩ ... ⟨ パターンn ⟩ -> e
と同じである．(let についても同様にパターンを空白で区切って並べることがで
きる．)
また，関数適用も (((f x) y) z) と書く代りに f x y z と，括弧を省略する
ことができる．(別の言い方をすると，関数適用式は左結合する．)
関数型構築子は，既に見たように，右結合し，
t1 -> t2 -> t3 -> t4 は t1 -> (t2 -> (t3 -> t4)) を意味する．
中置/前置演算子
これまで，なんの説明もなしに使ってきたが，+, ^ などの中置演算
子(infix operator) は，内部ではカリー化された関数 (int->int->int など
の型をもつ) として定義されている．さらに，プログラマが新たな中置演算子を
定義したり，(勧められないが) + などを再宣言することすらも可能である．
中置演算子は ( と ) で囲むことによって，通常の関数として(前置記法)で
使うことができる．
# (+);;
- : int -> int -> int = <fun>
# ( * ) 2 3;;
- : int = 6
* の前後に空白が入っているのは，コメントの開始/終了と区別するためである．
中置演算子として使用可能な記号は，mod, lor, or などの前章までに
中置演算子として紹介したキーワード，もしくは
-
1文字目が =, <, >, @, ^, |, &, +, -, *, /,
$, % のいずれかで，
- 2文字目以降が !, $, %, *, +, -, ., /, :, <, =,
>, ?, @, ^, |~ のいずれか
を満たす文字列である．
定義をするには (⟨ 中置演算子 ⟩) を普通の名前だと思って行う．
# let (^-^) x y = x * 2 + y * 3;;
val ( ^-^ ) : int -> int -> int = <fun>
# 9 ^-^ 6;;
- : int = 36
また，前置演算子といって，定義するときや単独で関数値として使うときは ()
が必要な，記号列からなる名前が用意されている．
# let ( !! ) x = x + 1;;
val ( !! ) : int -> int = <fun>
# !!;;
Characters 2-4:
!!;;Syntax error
# (!!);;
- : int -> int = <fun>
# !! 3;;
- : int = 4
前置演算子は -, -. もしくは
-
1文字目が !, ?, ~ のいずれかで，
- 2文字目以降が !, $, %, *, +, -, ., /, :, <, =,
>, ?, @, ^, |~ のいずれか
からなる文字列である．一見，前置演算子は関数の名前として記号が使うため
のものだけのように見えるが，実際は構文解析で違いが現れる．
前置演算子は通常の関数適用よりも
結合の優先度が高く，f !! x は，f (!! x) と解釈される．
(f g x が (f g) x と解釈されることと比較せよ．)
中置演算子同士の優先度は，名前から決まる．表4.1は
優先度の高いものから並べたものである．コンストラクタなど，未出の概念，記号
がでてきているがとりあえず無視しておいてよい．
Table 4.1: 演算子の優先順位と結合
| 演算子 |
結合 |
| 前置演算子 |
– |
| 関数適用 |
左 |
| コンストラクタ適用 |
– |
| 前置演算子としての -, -. |
– |
| ** で始まる名前 |
右 |
| *, /, %, で始まる名前および mod |
左 |
| +, - で始まる名前 |
左 |
| :: |
右 |
| @, ^ で始まる名前 |
右 |
| =，< など比較演算子, その他の中置演算子 |
左 |
| not |
– |
| &, && |
左 |
| or, || |
左 |
| , |
– |
| <-, := |
右 |
| if |
– |
| ; |
右 |
| let, match, fun, function, try |
– |
4.1.4 Case Study: Newton-Raphson法
高階関数の有効な例として，方程式の近似解を求める Newton-Raphson 法
をプログラムしてみよう．Newton-Raphson 法は，微分可能な関数 f に
対して，方程式 f(x) = 0 の解を求める方法であり，
の不動点 (g(a) = a なる a) を求める．(もしくは
漸化式 xn = xn−1 − f(xn−1) / f'(xn−1) の
極限を求める．)
これを解くプログラムを考えてみよう．まず，微分をどう表現するかであるが，
近似的に，とても小さい定数 dx に対して
としよう．微分を求める関数は，自然に次のような高階関数として定義できる．
# let deriv f =
# let dx = 0.1e-10 in
# fun x -> (f(x +. dx) -. f(x)) /. dx;;
val deriv : (float -> float) -> float -> float = <fun>
例えば f(x) = x3 の 3 における微分係数は，
# deriv (fun x -> x *. x *. x) 3.0;;
- : float = 26.999913416148047
と計算される．
次に不動点を求める関数を定義してみよう．この関数は，関数 f と
初期値 x から，f(x), f(f(x)), ...を計算していき，
fn(x) = fn−1(x) となったときの fn(x) を返す．
実数の計算には誤差が伴うので実際には，ある時点で |fn−1(x) − fn(x)|
がある閾値以下になったときに終了とする．
# let fixpoint f init =
# (* computes a fixed-point of f, i.e., r such that f(r)=r *)
# let threshold = 0.1e-10 in
# let rec loop x =
# let next = f x in
# if abs_float (x -. next) < threshold then x
# else loop next
# in loop init;;
val fixpoint : (float -> float) -> float -> float = <fun>
さて，これを使って，Newton-Raphson 法で用いる不動点を求める
べき関数は元の関数から
# let newton_transform f = fun x -> x -. f(x) /. (deriv f x);;
val newton_transform : (float -> float) -> float -> float = <fun>
で計算できる．
最終的に，Newton-Raphson 法で f(x) = 0 の解を求める
関数は，関数 f と初期値として用いる guess を受け取って
# let newton_method f guess = fixpoint (newton_transform f) guess;;
val newton_method : (float -> float) -> float -> float = <fun>
と定義できる．
# let square_root x = newton_method (fun y -> y *. y -. x) 1.0;;
val square_root : float -> float = <fun>
# square_root 5.0;;
- : float = 2.23606797750364272
Exercise 1 実数上の関数 f に対して ∫abf(x)dx を計算す
る関数 integral f a b を定義せよ．またこれを使って，
∫0πsinx dx を計算せよ．
近似的な計算方法として，ここでは台形近似を説明するが他の方法でも良い．
台形公式では b−a を n 分割した区間の長さを δ
として，台形の集まりとして 計算する．i番目の区間の台形の面積は
|
|
⎛
⎝ |
f |
⎛
⎝ |
a+ |
⎛
⎝ |
i−1 |
⎞
⎠ |
δ |
⎞
⎠ |
+ f |
⎛
⎝ |
a+iδ |
⎞
⎠ |
⎞
⎠ |
⋅ δ |
|
|
| 2 |
|
Exercise 2 練習問題7の pow
関数をカリー化して定義せよ． 次に第一引数が指数になるよう(pow n x)に定義し，3乗する関数 cube を部分適用で
定義せよ．指数が第二引数であるように定義されている場合
(pow x n)，cube を pow から定義するには どうすればよいか?
Exercise 3 以下の3つの型
-
int -> int -> int -> int
- (int -> int) -> int -> int
- (int -> int -> int) -> int
の違いを説明せよ．また，各型に属する適当な関数を定義せよ．
いろいろな関数を書いていくと，引数の型に関わらず同じことをする関数が出
現する場合がしばしば現れる．例えば，二つ組から第一要素を取出す関数を
考えてみよう．例えば，int * int に対するこのような関数は，
# let fstint ((x, y) : int * int) = x;;
val fstint : int * int -> int = <fun>
と書ける．明示的に型を宣言しているのは，意図的である．
また，(int * float) * string のような組と文字列の組に対して
同様な関数を定義すると
# let fst_ifs ((x, y) : (int * float) * string) = x;;
val fst_ifs : (int * float) * string -> int * float = <fun>
と書ける．さて，ここまでくると生じる疑問は，組の要素の組み合わせごとに
いちいち別の第一要素を取り出す関数をかかなければいけないのだろうか?と
いうことである．これらの関数は引数の型を除いて同じ格好をしている．それ
ならば，共通部分はひとつの定義におさめ，差異をパラメータ化できないだろ
うか? パラメータ化するとしたら，パラメータは一体なんであろうか?
注意深く考えると，この共通の定義は引数の「型」，より正確には第一要素
と第二要素の型(intとint，または int * float と string)に関して
パラメータ化することになることがわかるだろう．また，このパラメータとし
ては今までの関数とは異なり，「型を表現する変数」のようなものが必要なことが
わかる．これを明示的に書き表したのが下の関数宣言である．
# let fst ((x, y) : 'a * 'b) = x;;
val fst : 'a * 'b -> 'a = <fun>
'a と 'b が型変数(type variable)と呼ばれるものである．
このような「型に関して抽象化された関数」を多相的関数(polymorphic function)と呼ぶ．この fst の型 'a * 'b -> 'a は
「任意の型 T1, T2 に対して，T1 * T2 -> T1」と読むことができる．
(論理記号を使うならば ∀'a.∀ 'b.('a * 'b -> 'a) と考える
のがより正確である．)
実は，Objective Caml の型推論機能はこのような多相的関数の宣言に際しても，
明示的に型変数を導入する必要はない．
# let fst (x, y) = x;;
val fst : 'a * 'b -> 'a = <fun>
通常の「式に関して抽象化された関数」を適用する際に，実引数，つまりパラ
メータの実際の値を渡すのと同様，多相的関数には「型の実引数」を渡すと考
えられるが，実際のプログラムでは，型引数を明示的に書き下す必要はない．
(書き下すための文法は用意されていない．)
# fst (2, 3);;
- : int = 2
# fst ((4, 5.2), "foo");;
- : int * float = (4, 5.2)
概念的には，最初の例では 'a, 'b に int が，次の例では 'a に
int * float，'b に string が渡っていると考えることができる．
別の見方をすると，fst という式が，二つの違った型の式int * int -> int と (int * float) * string -> int * float として使
われていると見ることができる．このように一つの式が複数の型を持つことを
言語に多相性(polymorphism)がある，という．また，特に，関数の
型情報の一部をパラメータ化することによって発生する多相性をパ
ラメータ多相(parametric polymorphism)と呼ぶ．パラメータ多相の関数は
型変数に何が渡されようともその振舞いは同じであるという特徴がある．
多相性は，ひとつの定義の(再)利用性を高めるのに非常に役立つ．
いくつか多相性のある関数の例をみてみよう．以下の id は恒等関数(
identity function)とよばれ，
与えられた引数をそのまま返す関数である．また，関数適用関数 apply は関数と
その引数を引数と受け取って，関数適用を行う．
# let id x = x;;
val id : 'a -> 'a = <fun>
# let apply f x = f x;;
val apply : ('a -> 'b) -> 'a -> 'b = <fun>
apply の型では，('a -> 'b) が f の型を，'a が x の型を示す．型変数
'a が，ふたつの引数 f と x の間の制約，つまり f は x に適用で
きなければならないことを表現していることに注意したい．
# abs;;
- : int -> int = <fun>
# apply abs (-5);;
- : int = 5
# apply abs "baz";;
apply abs "baz";;
^^^^^
This expression has type string but is here used with type int
関数の多相性はどこに由来するものであろうか? fst の定義をよく見ると，
本質的に，(x, y) というパターンの要請する引数に関する制約は，「二つ
組であること」だけで，各要素が整数であろうが，文字列であろうが，構わな
いはずである．また， 各要素 x, y に対して何の操作も行われていない
ため，それが唯一の制約である．また，apply の定義からはf に対する要
請は「x に適用できる関数であること」だけである．このように，パラメー
タ多相は，関数が引数の部分的な構造(組である，関数であること)のみで計算
が行われることに起因している．また型変数は，関数自身は操作しない部分の
構造を抽象化していると考えることができる．つまり 'a * 'b -> 'a という
型を見れば，その関数が引数の第一要素も第二要素も使わないことが
わかるのである．
様々な多相性
その他の多相性としては，多くの言語に見られる +
という一つの記号が整数同士もしくは実数同士の
足し算どちらでも使える，といったアドホックな多相性(ad-hoc
polymorphism)
と呼ばれるもの，オブジェクト指向言語で見られる親子クラス関
係など，型上に定義された二項関係によって，式が複数の型を持ちうる
部分型多相(subtyping polymorphism) といったものがある．
Objective Caml では多相性を持てるのは，let(宣言もしくは式)で導入された
定義のみである．関数のパラメータを多相的に使うことはできない．
具体的には，下の例で x を(id が来るとわかっていても)異なる型の値への
適用は許されない．
# (fun x -> (x 1, x 2.0)) id;;
(fun x -> (x 1, x 2.0)) id;;
^^^
This expression has type float but is here used with type int
このエラーメッセージは，x 1 を型推論した時点で x の引数の型は
int として決定されてしまったのに，float に対して適用している，という
意味である．
また，任意の let 宣言/式でよいわけではなく，定義されるもの(右辺)が
「値」でなければいけない，という制限3がある．値として扱われるものは，関数の宣言，定数，など計算
を必要としない式である．逆に許されないものは，関数適用などの，値に評価
されるまでに計算を伴う式である．以下の例はf を x に二度適用する
double 関数である．
# let double f x = f (f x);;
val double : ('a -> 'a) -> 'a -> 'a = <fun>
# double (fun x -> x + 1) 3;;
- : int = 5
# double (fun s -> "<" ^ s ^ ">") "abc";;
- : string = "<<abc>>"
さらに，この関数を組み合わせると，同じ関数を4度適用する関数として用いること
ができる．
# double double (fun x -> x + 1) 3;;
- : int = 7
# double double (fun s -> "<" ^ s ^ ">") "abc";;
- : string = "<<<<abc>>>>"
ところがこの double double を let でそのまま宣言しても，右辺が関数
適用であり，値ではないので，多相的につかうことはできない．
# let fourtimes = double double in
# (fourtimes (fun x -> x+1) 3,
# fourtimes (fun s -> "<" ^ s ^ ">") "abc");;
fourtimes (fun s -> "<" ^ s ^ ">") "abc");;
^
This expression has type int but is here used with type string
これを let式ではなくて let 宣言した場合も同様な制限が課せられる．
# let fourtimes = double double;;
val fourtimes : ('_a -> '_a) -> '_a -> '_a = <fun>
アンダースコアのついた型変数 '_a は，「一度だけ」任意の型に置換できる
型変数であり，一度決まってしまうと二度と別の型として使うことはできない．
このため，多相的に fourtimes を使用することはできない．
# fourtimes (fun x -> x + 1) 3;;
- : int = 7
# fourtimes;;
- : (int -> int) -> int -> int = <fun>
# fourtimes (fun s -> "<" ^ s ^ ">") "abc";;
fourtimes (fun s -> "<" ^ s ^ ">") "abc";;
^
This expression has type int but is here used with type string
fourtimes の型変数が一度目の適用で int に固定されてしまっている．
この制限を値多相(value polymorphism)と呼ぶ．値多相に制限しな
ければならない理由は副作用(7章参照)をもつ言語機構
と深く関係があるのだが，ここでは説明しない．fourtimes のような定義に
多相性を持たせるためには，
# let fourtimes' f = double double f
# (* equivalent to "let fourtimes' = fun f -> double double f" *) ;;
val fourtimes' : ('a -> 'a) -> 'a -> 'a = <fun>
のように，明示的にパラメータを導入して，関数式として
(つまり fun を使って)定義してやればよい．
# fourtimes' (fun x -> x + 1) 3;;
- : int = 7
# fourtimes' (fun s -> "<" ^ s ^ ">") "abc";;
- : string = "<<<<abc>>>>"
このように，値が関数であるような式(ここでの double double)に
fun x -> ... x をつけて値とするような(プログラムの)変換を
η-展開(η-expansion)という．
さて，これまで Objective Caml では型推論の機能があり，プログラマは関数の引数の
型を特に明示的に宣言しなくてもよいことには触れたが，それがどのような仕組みで
実現されているかについては詳しく述べなかった．ここでは，簡単に型推論の
仕組みを見る．
まず簡単な例から考えてみよう．fun x -> x + 1 という式はもちろん int -> int
型を持つわけだがこれがなぜか考えてみると，ひとつの考え方として
-
+ は int -> int -> int 型だから両辺に int が来なければならない．
- x の型は与えられていないが，+ の左側にあるから，x は int でなければならないはずだ．1 も同様に int でなければならないが，これはOKだ．
- x が int であると仮定すれば，x + 1 は int になる．
- x + 1 を int でなければならない x で抽象化するから，全体の型は
int -> int である．
という，推論が成り立つ．Objective Caml はまさにこのように型推論を行っている．
より具体的には，式をボトムアップに見ていく．定数 1 などはその型が
自明に与えられ，変数に関してはとりあえず，未知の型
を表す新しい型変数を割り当てる．関数適用や if式など，
部分式から構成される個所で，部分式の型に関する制約(「x の型 'a は int
でなければならない」など)を構成し，それを解く．もしも制約が解けない場合は，
その式は型があっていないと結論づけられる．制約が解けない例は
fun x -> if x then 1 else x
を考えるとわかる．if式の型規則は if 直後の式は bool に等しく，
then節，else節の型も等しい，というものであるから，x に割り当てら
れた型変数を 'a とすると，int = 'a = bool という制約が得られる．
これは明らかに解くことができないので，この式は型エラーとなる．
制約を解いても型変数が残る場合がある．この式が値で，かつ let で宣言される
ものであれば，この型変数は型パラメータとして(暗黙の内に)抽象化される．
例えば，先ほどの apply の宣言は，
f, x の未知の型をそれぞれ 'a, 'b とすると f x という式から，
f x の型を 'c として，'a = 'b -> 'c という制約と
fun f x -> f x 全体の型 'a -> 'b -> 'c が導かれる．これを
書き換えて，('b -> 'c) -> 'b -> 'c となる．
ひとつの式には(型エラーを起こさない範囲で)様々な型が割当てられる可能性
があるわけだが，それらの候補のうちには「一般性・汎用性」の高いものと低
いものがある．例えば，fst関数に対しては，int * int -> int，float * int -> float， 'a * 'a -> 'a といった型が与えられるが，こ
れらは 'a * 'b -> 'a よりも(適用できる場所が少ないという意味で)一般
性の低い型である．例えば 'a * 'a -> 'a という型は引数の組の要素の型
が等しいような引数にしか適用できないという，本来なら不必要な制限がつい
ている分，'a * 'b -> 'a という型よりも汎用性が低いと考えられる．
与えられた式の最も一般的な型(が存在する場合，その型)のことを
主要な型(principal type)と呼ぶ． Objective Caml (や Standard ML,
Haskell) では，与えられた式には常に主要な型が存在することが保証されて
おり，また，型推論アルゴリズムは，上で述べたような方法で，
主要な型を常に求めることができるという，良い性質を持っている．
型推論の長所・短所
ところで，型推論は変数の型宣言を省ける一方，型宣言そのものはプログラム
を読む上でも有用なものである．どのような場合に宣言をすべき/しないべき
かは，趣味の問題である部分もあるが，高階関数/匿名関数を使うようになる
と，型が文脈から自明な場合が多く現れる．たとえば，先ほどの
Newton-Raphson 法で，
let square_root x = newton_method (fun y -> y *. y -. x) 1.0;;
のように高階関数 newton_method に，匿名関数を渡している．
newton_method の型から匿名関数のパラメータ y の型が float で
あることはすぐわかる．ここで，わざわざ fun (y : float) -> ... と
書かなければならないとしたら結構面倒である．
また，主要な型を求める一番確実な方法は，型宣言をしないことである．先ほ
どの fst を
# let fst ((x, y) : 'a * 'a) = x;;
val fst : 'a * 'a -> 'a = <fun>
と宣言しても，型チェックを通過するが，組の要素が同じ型を持たなくてはな
らないという，一般性を欠く定義になってしまう．
# fst (true, 3.2);;
fst (true, 3.2);;
^^^^^^^^^^^
This expression has type bool * float but is here used with type bool * bool
この反面，ML型推論は，型検査によるエラーが思わぬところで報告される，
という欠点がある．例えば，前の例の変形だが，
# fun x -> (x 1, x true);;
fun x -> (x 1, x true);;
^^^^
This expression has type bool but is here used with type int
で，x true でエラーが報告されているが，もしかすると，x 1 で1 を
渡している部分で間違えたのかもしれない．特に定義が大きくなりx 1
と x true が離れているような場合，「本当に間違えたところ」を一目で探
すのが難しい場合がある．これは，しばしば ML の型推論の欠点として指摘さ
れる点である．(熟練した Objective Caml プログラマは，型推論がどのようにして
行なわれるかを理解しているため，それほど惑わされずに本当のエラー箇所を
探しあてることができる．) これに対し，x の型を宣言し，
# fun (x: bool -> 'a) -> (x 1, x true);;
fun (x: bool -> 'a) -> (x 1, x true);;
^
This expression has type int but is here used with type bool
とすれば，x の取る引数の型が予めわかっているので，x 1 の部分でエラー
が報告される．
4.2.3 Case Study: コンビネータ
「計算」という概念のモデルとして基本的なものにチューリング機械がある．
チューリング機械は，CPUがメモリの読み書きをしながら計算を進めて行く
様子を単純化したものである．これに対して，関数型プログラミングの計算
をモデル化したものに λ計算，コンビネータ理論といったものがある．
λ計算の体系は関数適用におけるパラメータの引数の置換をモデル化し
たもので，複雑な計算も関数抽象式(Objective Caml の fun 式)と関数適用の組み合わせ
のみで表すことができる．コンビネータ理論は，λ計算の理論と
密接に関わっていて，コンビネータと呼ばれるいくつかの「関数を組み合わせて新しい
関数を構成する」高階関数の組合わせで，複雑な計算を表現するものである．
ここでは簡単にコンビネータについてみていく．
最もよく知られたコンビネータのひとつは数学で使う関数合成
f ∘ g (但し，(f ∘ g)(x) = f(g(x)) とする)を表す ∘ である．これは，関数 f, g からそれらを合成した関数を構成する
コンビネータと考えられる．∘ を中置演算子$で
表現することにすると，
let ($) f g x = f (g x);;
val ( $ ) : ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b = <fun>
と表現される．例えば，二つの関数の組合わせからなる関数
fun x -> ~-. (sqrt x)
は，
# let f = ( ~-. ) $ sqrt;;
val f : float -> float = <fun>
# f 2.0;;
- : float = -1.41421356237309515
という式で表現できる．(~-. は実数値の符号を逆転させる単項演算子であ
る．)コンビネータのポイントは，明示的にパラメータを導入することなく，
単純な関数を組み合わせてより複雑な関数を構成できるところにある．
もっとも単純なコンビネータは先に見た id である．(コンビネータ理論では I
コンビネータと呼ばれる．) id f は f と同じ関数を表現する．また
I コンビネータは関数合成と組み合わせても何も起らない．
# (sqrt $ id) 3.0
# (* Without (), it would be equivalent to sqrt $ (id 3.0) *)
# ;;
- : float = 1.73205080756887719
# (id $ sqrt) 3.0;;
- : float = 1.73205080756887719
K コンビネータは定数関数を構成するためのコンビネータであり，以下の関数
で表現される．
# let k x y = x;;
val k : 'a -> 'b -> 'a = <fun>
k x は何に適用しても x を返す関数になる．
# let const17 = k 17 in const17 4.0;;
- : int = 17
次の S コンビネータは関数合成の ∘ を一般化したものである．
# let s x y z = x z (y z);;
val s : ('a -> 'b -> 'c) -> ('a -> 'b) -> 'a -> 'c = <fun>
Objective Caml で fun 式と関数適用の組合わせ「のみ」で表現できる関数 (fun x -> x, fun x y -> x (x y) など)は Sと K の組合わせの
みで表現できることが知られている．これらは，単純型付きλ計算
で表現できる関数のクラスと同じである．例えばIコンビネータは S
K K として表せる．
# s k k 5;;
- : int = 5
(不動点コンビネータを導入した)コンビネータ，(型なしの)
λ計算はチューリング機械と同程度の表現力がある
計算モデルであることが知られている．
Exercise 4 以下の関数 curry は，与えられた関数をカリー化する関数である．
# let curry f x y = f (x, y);;
val curry : ('a * 'b -> 'c) -> 'a -> 'b -> 'c = <fun>
# let average (x, y) = (x +. y) /. 2.0;;
val average : float * float -> float = <fun>
# let curried_avg = curry average;;
val curried_avg : float -> float -> float = <fun>
# average (4.0, 5.3);;
- : float = 4.65
# curried_avg 4.0 5.3;;
- : float = 4.65
この逆，つまり (2引数の)カリー化関数を受け取り，二つ組を受け取る関数に
変換する uncurry 関数を定義せよ．
# let avg = uncurry curried_avg in
# avg (4.0, 5.3);;
- : float = 4.65
Exercise 5
以下の関数 repeat は double, fourtimes などを一般化したもので，
f を n 回，x に適用する関数である．
# let rec repeat f n x =
# if n > 0 then repeat f (n - 1) (f x) else x;;
val repeat : ('a -> 'a) -> int -> 'a -> 'a = <fun>
これを使って，フィボナッチ数を計算する関数 fib を定義する．
以下の ... の部分を埋めよ．
let fib n =
let (fibn, _) = ...
in fibn;;
Exercise 6
次の関数 funny がどのような働きをするか説明せよ．
# let rec funny f n =
# if n = 0 then id
# else if n mod 2 = 0 then funny (f $ f) (n / 2)
# else funny (f $ f) (n / 2) $ f;;
val funny : ('a -> 'a) -> int -> 'a -> 'a = <fun>
Exercise 7 s k k が恒等関数として働く理由を s k k 1 が評価される
計算ステップを示すことで，説明せよ．
また，fun x y -> y と同様に働く関数を，コンビネータ s と k を
関数適用のみで(fun や let による関数定義を使わずに)
組み合わせた形で表現せよ．
# ( (* s, k を 関数適用で組み合わせた式 *) ) 1 2;;
- : int = 2
Exercise 8
double double f x が f (f (f (f x))) として働く理由を前問
と同様にして説明せよ．
- 1
- 関数名を考えるのって面倒じゃありませんか？
- 2
- この考えは Sch�nfinkel という人が発見した
らしいがなぜが Curry 化と呼ばれている．
- 3
- 実は，現在演習で使用して
いるバージョン 3.08.1では，もう少し制限が緩くなっていて，値とある種
の型を持つ式に多相性が許されるようになっているが，ここでは細かくは触
れない．