Javaプログラマーのための圏論(4.クライスリ圏)
クライスリ圏
これまで型と純粋関数を圏としてモデル化する方法を見てきた。圏論で副作用、また非純粋関数をモデル化する方法があることも触れた。次のような例:実行時のログまたはトレースをする関数を見てみよう。javaでは次のようにグローバルに状態を変更して実装するだろう。
String logger; Boolean negate(Boolean b) { logger += "Not so! "; return !b; }
参照透過性(同じ入力に対して同じ作用と同じ出力とを持つこと)が成り立たないので、この関数は純粋関数ではない。
現代では、グローバルな状態を変更するのをできるだけ避けようとする(並列の複雑さのため)。ライブラリではこのようなコードは決して使われない。
幸いにも、このような関数を純粋関数にすることができる。引数と戻り値で明示的にログを通過させればよい。文字列の引数を追加して、更新されたログを含む文字列とペアにして戻せばよい。
class Pair<A, B> { final A first; final B second; Pair(A first, B second) { this.first = first; this.second = second; } } Pair<Boolean, String> negate(Boolean b, String logger){ return new Pair<>(!b, logger + "Not so! "); }
この関数は純粋で、副作用を持たず、同じ引数で呼び出されれば毎回同じペアを返し、必要なら記憶することもできる。けれども、ログは累積していくものであることを考慮すると、ある呼び出しを引き起こすことができるようなすべての可能な履歴を記憶しなければならない。次のようにそれぞれ別々のエントリになる。
negate(true, "It was the best of times. "); negate(true, "It was the worst of times. ");
また、ライブラリでのインターフェースとしても余り良くない。呼び出される関数は戻り値の型のその文字列を無視したいが、引数としての文字列を通過させなければならず、便利ではない。
ログの追加するのをより軽減して同じことをする方法はないか?関心事を分離すること方法はないか?この単純な例では、関数の主な目的はあるブール値を別のブール値に変換することである。ログを残すのは副次的なことである。その関数で特定されるメッセージは決まっているが、ある連続するログの中にそのメッセージを追加する処理と別の関心事である。その関数が文字列を生成したいが、ログを生成することの負担は避けたい。妥協すると以下のようになる。
Pair<Boolean, String> negate(Boolean b) { return new Pair<>(!b, "Not so! "); }
ログは関数の呼び出しの間で集約されるだろうと言う発想である。
もう少し現実的な例を見てみよう。小文字を大文字に変換する関数と文字列を空白の区切り文字で文字列の配列に分割する関数で取り上げる。
String toUpper(String s) { return s.toUpperCase(); } String[] toWords(String s) { return s.split(" "); }
関数toUpperとtoWordsを変更することで、正規な戻り値の最上位にメッセージ文字列を上に載せるようにしたい。これらの関数の戻り値を「装飾する」。次のように総称型でWriterを定義すれば、最初の任意の型Aの値と二つ目の文字列型の値のペアをカプセル化する。
class Writer<A> extends Pair<A, String> { Writer(A v, String s) { super(v, s); } }
これを使って装飾する。
Writer<String> toUpper(String s) { String result = s.toUpperCase(); return new Writer(result, "toUpper "); } Writer<String[]> toWords(String s) { String[] result = s.split(" "); return new Writer(result, "toWords "); }
これらの二つの関数を合成して、別の装飾された関数、を大文字にして単語に分解する、そしてこれらの操作のログを生成する関数にしたい。それは次のようにするかもしれない。
Writer<String[]> process(Stirng s) { var p1 = toUpper(s); var p2 = toWords(p1.first); return new Writer(p2.first, p1.second + p2.second); }
我々が達成したいゴールは次のようなものである。ログの集約は個々の関数の関心事ではない。これらはそれぞれのメッセージを生成し、その後このメッセージはより大きなログに外部で連結される。
このようなスタイルのプログラム全体を想像して欲しい。繰り返しと間違いをおこしやすいコードの悪夢である。しかし我々はプログラマーである。繰り返しのコードを扱う方法を知っている。それを抽象化すればよい。けれども、これはありふれた抽象化ではない。関数の合成を抽象化するのである。合成は圏論の核心である。より多くのコードを書く前に、圏論の視点からその問題を解析してみよう。
Writer圏
追加機能を上に載せるために一連の関数の戻り値を装飾する発想はとても良い結果をうむことがわかる。そのような例をこれから提示していくつもりである。出発点は型と関数の正則圏である。対象としての型の話題を置いておき、装飾された関数で射を再定義する。
例えば、Integer
からBoolean
を得るisEven
と言う関数を装飾してみよう。この関数は装飾された関数で表される射に変化する。重要な点は、この射がInteger
とBoolean
の対象の間での矢印として依然として見なせることである。この装飾された関数が次のようにペアを返すとしてもである。
Pair<Boolean, String> isEven(Integer n){ return new Pair<>(n % 2 == 0, "isEven "); }
圏の法則により、この射はBoolean
の対象から任意の対象を得る別の射と合成出来るはずである。特に、次のような先に述べたnegate
で合成できるはずである。
Pair<Boolean, String> negate(Boolean b){ return new Pair<>(!b, "Not so! "); }
明らかにこれらの射は通常の関数と同じように合成することは出来ない。入力と出力が一致しないからである。これらの合成は次のようなものになるべきである。
Pair<Boolean, String> isOdd(Integer n) { Pair<Boolean, String> p1 = isEven(n); Pair<Boolean, String> p2 = negate(p1.first); return new Pair<>(p2.first, p1.second + p2.second); }
ここで行った圏論で2つの射の合成の手順は次のようなもので構成されている。
1. 最初の射に対応する装飾された関数を実行する。
2. 結果のペアの最初の要素を取り出して、2番目の射に対応する装飾された関数に渡す。
3. 最初の結果の2番目の要素(文字列)と2番目の結果の2番目の要素(文字列)を連結する。
4. 最後の結果の最初の要素と連結した文字列を一緒にして新たなペアを作って戻す。
Javaでこの合成を抽象化したいなら、ここでの圏の3つの対象に対応する3つの型による総称型を使う必要がある。ここで触れた規則に従う合成できる2つの装飾された関数を引数とし、3番目の関数を戻すような関数である。
<A,B,C> Function<A, Writer<C>> compose(Function<A, Writer<B>> m1, Function<B, Writer<C>> m2) { return x -> { var p1 = m1.apply(x); var p2 = m2.apply(p1.first); return new Writer<C>(p2.first, p1.second + p2.second); }; }
ここで以前に触れた例に戻り、toUpperとtoWordsの合成をこの新しいテンプレートを使って実装すると、次のようになる。
Writer<String[]> process(String s) {
return compose<String, String, String[]>>(toUpper, toWords)(s);
}
合成のテンプレートに型を渡すための無駄が多い。一般化されたラムダ関数を使うと総称型の指定を削減できる。
const var compose = (m1, m2) -> { return x -> { var p1 = m1.apply(x); var p2 = m2.apply(p1.first); return new Writer<C>(p2.first, p1.second + p2.second); } }
この新しい定義では、processの実装はもっとシンプルになる。
Writer<String[]> process(String s){
return compose(toUpper, toWords)(s);
}
まだ終わっていない。新たな圏で合成を定義したが、恒等射はどうなる?正規な恒等射は存在しない。型A
から型A
へ戻す射で、次のような装飾された関数である。
Writer<A> identity(A);
合成の観点で単位元のように振る舞わなければならない。先に定義した合成を見ると、恒等射は引数を変更しないでそのまま戻し、ログには空の文字列を与えなければならない。
<A> Writer<A> identity(A x){ return new Writer(x, ""); }
ここで定義した圏が本当に正当な圏であることが納得できるだろう。特に、合成の結合律を満たすことは自明である。各ペアの1番目の要素では正規の関数の合成であり、それは結合律が成り立つ。2番目の要素は連結であり、連結もまた結合律が成り立つ。
文字列に限定せず、任意のモノイドに対して容易にこのような一般化が出来ることに気づいたかもしれない。compose
の中はmappend
、identity
の中はmempty
を使える(+
と""
を置き換える)。文字列のログを残すことに限定する必要もない。良いライブラリであれば、ライブラリの働きをするのに最低限の制約だけ課せばよい。ここでは、ログライブラリの要求はログがモノイドの性質を持つことである。
クライスリ圏
この圏は発明したものではなく、クライスリ圏と呼ばれる例である。クライスリ圏はモナドに基づく圏である。まだモナドについて議論するのに準備が整っていないが、モナドがどのようなものか雰囲気を感じてもらいたかった。限定的な目的に対して、クライスリ圏は対象として、根本的なプログラミング言語の型を持つ。型Aから型Bへの射は型Aから特別な装飾が行われた型Bから派生した型への関数である。クライスリ圏は独自のやり方でこのような射の合成を定義し、またその合成の観点で恒等射を定義した。(後で「装飾」と言う不正確な用語が圏における自己関手に対応することを触れる予定である。)
ここで述べた圏の基本的な内容を説明するのに使った特別なモナドはWriterモナドと呼ばれ、関数の実行のログを残したり、トレースしたりするものとして使われている。純粋な計算の効果を埋め込むためのより一般的なメカニズムもある。集合の圏でプログラミング言語の型と関数をモデル化できるのは既に見てきた。このモデルを少し異なった圏に拡張する。装飾された関数で表される射を持つ圏で、その合成は単にある関数の出力から別の関数の入力へ通過出来るだけではない。合成そのものの自由度を引き上げた。この自由度のおかげで、命令型プログラミング言語で従来副作用を使って実装されていたプログラムに対して単純な表示的意味論を与えることが出来たのである。