bitterharvest’s diary

A Bitter Harvestは小説の題名。作者は豪州のPeter Yeldham。苦闘の末に勝ちえた偏見からの解放は命との引換になったという悲しい物語

Haskellで学ぶ圏論・ウォームアップ編 二項演算子とカリー化

1.ハスケル・カリー

関数型プログラミング言語Hasekllの名前は、アメリカの数学者ハスケル・カリーに因んでいる。ハスケルアメリカのハーバード大学を卒業した後、ドイツのゲッティンゲン大学で著名な数学者ヒルベルトの下で博士号を授与されている(ゲッティンゲン大学は1737年にハノーファー選帝侯ゲオルク・アウグストによって設立され、ノーブル賞受賞者45人を輩出する世界でも有数の大学)。

ハスケル・カリーに因んで、もう一つ有名な数学での専門用語がある。これは苗字に因んだもので、カリー化と呼ばれる用語である。Haskellを学ぶと割合と最初で出会うことになるがが、初心者にとっては何となくすっきりと頭に入ってこない概念の一つである。その主な理由は、なぜ、そのようなことが必要なのかがあまり説明されていないためのように思える。ここでは、二項演算子とカリー化の考え方について説明したいと思う。

2.カリー化

簡単のために加算を例にとって話を進める。小学校の時に習った加算は3+4のように演算子+を真ん中に置き、足される数3と足す数4を、演算子の左と右にそれぞれ置いた。このような演算子二項演算子あるいは中置演算子と呼ぶ。これに対して、普通の関数のように、演算子を左側において足される数と足す数をそれに続けて書くこともHaskellでは許されている(但し、+はカッコで囲む必要がある)。その場合には、次のように書く。

(+) 3 4

このように記述すると、加算は演算子というよりも関数のように見えると思う。

ところで、一般に、関数での引数の数はまちまちである。あるものは一つであるし、あるものは複数であるし、ないものもある。しかし、四角四面の人は自由度が多いことを気に入らないであろう。できれば、引数の数は定められていた方が都合がよいと思う場合もなくはない。そこで、引数の数は一つに限定しようというのが、カリー化である。

先の加算を例にすると、3に加えるという関数(3+)、あるいは、4を加えるという関数(+4)を用意すればよい。このような関数を実際実行してみると次のようになる。

Prelude> (3+) 4
7
Prelude> (+4) 3
7

このような例は他の四則演算でも確認できる。例えば、除算では次のようになる。

Prelude> (/15) 60
4.0
Prelude> (40/) 5
8.0

また、minやmaxでも同じことがいえる。例えば、15と4のうちで小さいほうを選ぶときは通常は次のようにする。

Prelude> min 15 4
4
Prelude> :t min
min :: Ord a => a -> a -> a

また、型シグネチャからもminは二つの引数をとっていることが分かる。しかし、これをカリー化すると、例えば、15との比較で小さい数をとる関数は(min 15)となる。この関数を用いて、4と比較すると次のようになる。

Prelude> (min 15) 4
4
Prelude> :t (min 15) 
(min 15) :: (Ord a, Num a) => a -> a

また、型シグネチャを見ても引数は一つであることが分かる。

カリー化すると、関数に入力される引数も、関数から出力される値も一つになるので、関数を簡単に合成できるようになる。圏論では、関数の合成は重要な要素なので、カリー化による利益は大きい。

3.カリー化された加算の構造

カリー化された加算の構造がどのようになっているかを見ていく。圏論では、ある圏(カテゴリー)の構造を見るとき、対象、射、射の合成などを定義しなければならない。そこで、カリー化された加算(ここでは整数に限ることとする)についてこれらを定義することとする。

(1) 対象
引数と関数の値(出力)が対象となるが、ここでは引数も整数であり関数の値も整数(整数同士の加算は整数のため)であるので、対象は整数の集まり\(\mathbb{Z}\)とする。即ち、対象は一つである。

(2) 射
射は関数であるので、\( (+a)\)、但し、\(a \in \mathbb{Z}\)とする。従って、射は無数に存在することとなる。

(3) ドメインとコドメイン
射のドメイン(射への入力)とコドメイン(射からの出力)は、対象のところで定めた\(\mathbb{Z}\)となる。

(4) 恒等射
自分から自分へ移す関数を恒等射というが、ここでは、\( (+0)\)となる。

(5) 合成
射\(f,g\)の合成\(g \circ f\)とは、射\(f\)を施した後、その結果に、射\(g\)を施す(但し、\(f\)のコドメインと\(g\)のドメインは同一である)ことだが、ここでも合成は許されるものとする。
例えば、射\( (+3)\)と射\( (+4)\)の合成とは(+3)を行った後、(+4)を行うことである。従って、ここでは、\( (+b) \circ (+a)\)は\( (+(b + a))\)となる。但し、\(a,b \in \mathbb{Z}\)である。

Haskellでは関数の合成はピリオド(.)である。関数の合成\( ( (+4) . (+3))\)と合成した関数\( (+7)\)をそれぞれHaskellで実行した結果は次のようになる。

Prelude> ((+4)  . (+3)) 5
12
Prelude> :t ((+4)  . (+3))
((+4)  . (+3)) :: Num c => c -> c
Prelude> (+ (3 + 4)) 5
12
Prelude> :t (+ (3 + 4))
(+ (3 + 4)) :: Num a => a -> a

この構造を表すと次のようになる。
f:id:bitterharvest:20150211132125p:plain

なお、圏となるためには二つの条件を満たさなければならない。一つ目の条件は単位律で、任意の射\(f:A \rightarrow B\)に対して、対象\(A\)への恒等射を\(id_A\)、対象\(B\)へのそれを\(id_B\)とした時、\(id_A \circ f = f = f \circ id_B \) を満たすことである(対象が一つしかない圏では、恒等射を\(id\)と記す場合もある。上記の加算はその例の一つである)。二つ目の条件は結合律で、合成できる任意の射\(f,g,h\)に対して、\((f \circ g) \circ h = (f \circ (g \circ h) \)を満たすことである。

カリー化された加算の場合にはこの二つの条件を満たすので、圏となっている。

4.カリー化された\(min \ a\)の構造

整数を対象にする\( (min \ a)\)について考えると、加算の場合と同じようにその構造を次のようになる。
f:id:bitterharvest:20150211132158p:plain
\( (min \ a\))では、
(1) 対象は整数の集まり\(\mathbb{Z}\)である。
(2) 射は\( (min \ a)\)、但し、\( a \in \mathbb{Z} \)とする。
(3) ドメインとコドメインは\(\mathbb{Z}\)である。
(4) 恒等射は\( (min \ \infty)\)である。
(5) 合成は\( (min \ b) \circ (min \ a)=(min \ (min \ b, a))\)となる。

加算の場合と同じように、関数の合成\( ( (min \ 3) . (min \ 4))\)と合成した関数\( (min \ 3)\)をそれぞれHaskellで実行した結果は次のようになる。

Prelude> ((+4)  . (+3)) 5
12
Prelude> :t ((+4)  . (+3))
((+4)  . (+3)) :: Num c => c -> c
Prelude> (+ (3 + 4)) 5
12
Prelude> :t (+ (3 + 4))
(+ (3 + 4)) :: Num a => a -> a

カリー化された\( (min \ a)\)も、圏になるための二つの条件を満たしているので、圏である。

\(max \ a\)についても同じことがいえる。

5.モノイド

モノイドとは、対象が一つだけ存在する圏である。四則演算、\(min, max\)などはすべて対象が一つであるので、モノイドに属す。

それでは、最初に戻って、中置演算子での\(3+4\)はどのように考えたらよいのだろうか。とりあえず準備として、原始的なモノイドを考える。これは次のようになっている。

(1) 対象
対象は一つで★とする。

(2) 射
整数の集まり\(\mathbb{Z}\)とする。

(3) ドメインとコドメイン
★とする。

(4) 恒等射
\(id\)とする(これは後で説明するが、合成の解釈によって異なる。例えば、\( \circ \)が\( + \)の時は0、\( \times \)の時は1、\( \min \)の時は\( \infty \)、\( \max \)の時は\(- \infty \)である)。

(5) 合成
任意の二つの射\(f,g\)に対して、合成\(g \circ f\)が許されるものとする。

原始的なモノイドは下の図で表すことができる。
f:id:bitterharvest:20150211173231p:plain

次に、原始的なモノイドの(1)-(4)はそのままとし、合成の部分、即ち、\( \circ \)を、加算+と解釈したモノイドを考える。このモノイドを図示すると次のようになる。
f:id:bitterharvest:20150211173835p:plain

具体的な数字を入れたのが下図である。
f:id:bitterharvest:20150211174518p:plain

上記の図から、原始的なモノイドでの合成を+とみなした時、中置演算子での加算の表現と同じになることが分かる。

さらに、圏となるための二つの条件(加算だけなので計算の順序によらない)も満たしているので、圏であることも分かる。

6.関手

加算についてカリー化した場合と中置演算子の場合の構造が分かったので、この二つの構造の関係を調べることにする。そこで、カリー化した圏\(\mathcal{C}_1\)から中置演算子の圏\(\mathcal{C}_2\)への写像\(F\)を考える。\(F\)は\(\mathcal{C}_1\)の対象\(\mathbb{Z}\)を\(\mathcal{C}_2\)の対象★へ、\(\mathcal{C}_1\)の射\( (+a)\)を\(\mathcal{C}_2\)の射\(a\)へ写像するものとする。この時、\(\mathcal{C}_1\)での任意の射\( (+a)\)と任意の射\( (+b)\)の合成\( (+b) \circ (+a)\)と、\( (+a)\)と\( (+b)\)を\(\mathcal{C}_2\)に\(F\)で写像したときの射\(F( (+a))\)と射\(F( (+b))\)の合成\(F( (+b)) \circ F( (+a))\)との関係を考える。なお、\(F( (+a))=a, F( (+b))=b\)である。

\(\mathcal{C}_1\)と\(\mathcal{C}_2\)の関係を下図に示す。
f:id:bitterharvest:20150212065910p:plain

そこで、次の結果を得る。
\begin{eqnarray*}
F( (+b)) \circ F( (+a)) &=& b \circ a \\
&=& (b + a) \\
&=& F( (+ (b + a))) \\
&=& F( (+b) \circ (+a))
\end{eqnarray*}

即ち、 \( F( (+b)) \circ F( (+a)) \) \( =F( \) \( (+b) \circ (+a) \) \( ) \)が得られた。このことから、\(\mathcal{C}_1\)での任意の射の合成が写像\(F\)によって\(\mathcal{C}_2\)での対応する射の合成に移されることが証明された。また、\(\mathcal{C}_2\)の全ての射が恒等射であることから、\(\mathcal{C}_1\)での恒等射(+0)は恒等射に写像される。この二つの性質を満たす時、一般に、\(F\)は関手と呼ばれる。関手は二つの圏\(\mathcal{C}_1\)と\(\mathcal{C}_2\)が同じ構造を持つことを保証する便利な関数である。\(F\)が関手である時、\(\mathcal{C}_1\)で計算をして(射を施して)その結果を\(F\)で写像したものと、それぞれを\(\mathcal{C}_2\)に移してそこで計算した(射を施した)結果とは一致する。この結果、計算のしやすいほうで計算してよいということを\(F\)は保証してくれる。