bitterharvest’s diary

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

Haskellの難関モナドを突破するために掘り下げて学ぶ(1)

10.モナドを掘り下げよう

圏論についての説明は前回の記事で一応終了した。しかし、ある事項についてはもう少し詳しく知りたいということがあるだろう。そのうちの一つはモナドだと思う。モナドは慣れてくるととても便利な道具なのだが、そこまでに行き着くのにはそれなりの努力が必要だ。そこで、ここでは、モナドについてもう少し踏み込んで説明しよう。

10.1 圏論とプログラム

まず、関数から説明することにしよう。Milewskiが面白いたとえを用いて説明しているので、それを利用させてもらおう。関数とは入力と出力があり、入力に対してある操作を加え、その結果を出力する。

ここからはMilewskiの説明をベースにして作った話だ。プログラマーが南の島へ旅行に行ったとしよう。島についた彼は、漁師たちから彼らを背の高い順に整列させて欲しいとせがまれた。彼はソートのアルゴリズムを利用して漁師を背丈で昇順になるように一列に並べた。上の例では、集まってきた漁師たちが入力、背丈の順に一列に並んだ漁師が出力、プログラマーが関数である。この関数を\(f\)としておこう。

同じように、漁師たちが収穫した魚の量によって彼らを一列に並べたとする。この時の入力はやはり集まった漁師たち、出力は収穫の量に応じて昇順に並んだ漁師、関数はプログラマーである。また、この関数を\(g\)としておこう。

圏論で重要な考え方の一つは、関数の合成である。複雑な作業は、いくつかの関数を繋ぎ合わせたもので構成される。例えば、漁師たちを収穫の量に応じて整列させるのだが、収穫量が同じ場合には背の高さで並んでいるようにしたいと考えたとしよう。この場合、上記の二つを用いて、関数\(f\)を適応した後に、その出力を関数\(g\)の入力とすればよいことに簡単に気が付くであろう(\(g\)の後に\(f\)を適応すると予想した結果にはならないことに注意)。二つの関数を連続して用いることを関数の合成と言い、この場合には\(g \circ f\)と書く。

このように、複雑な問題はより簡単な問題の合成へと分解することを繰り返すことで、難しい問題を解くことができるようになる。

ここで、Milewskiが突飛な例を出した。関数を動物とし、入力を食物、出力を排泄物としよう。さて、動物同士を繋げたらといった瞬間、聴衆の一人が笑いだし、止まらなくなった。

複雑な問題の解決はプログラムでも同じである。複雑なプログラムを設計するときは、これをより単純なサブプログラムの合成へと分解することで、上記の場合と同じように解決することができる。関数の合成は\( \circ \)で表したがプログラムの合成を\(>=>\)で表すことにしよう。プログラムも入力を出力に変えてくれる。ただ、異なるのは入力と出力の住んでいる世界が異なる点だ。例えば、整数の二乗を行うプログラムを考えよう。入力はコンピュータの世界で取り扱っている整数だ。これに対して出力は人間の世界が取り扱っている整数だ。整数という概念に対してはほぼ同じだが、その表し方は根本的に異なっている。そこで、コンピュータの世界での値\(a\)を人間の世界では値\(m \ a\)と表すことにしよう。なお、ここで\(m\)はモナドというコンテナで包んだというように解釈することにしよう。ただしモナドもコンテナもこれからの説明になるので、この段階では\(m\)は人間の世界で包んだという解釈にしておこう。

下図にプログラム\(f\)と入力\(a\)出力\(m \ b\)の関係を示した。
f:id:bitterharvest:20170805090020p:plain

また、プログラムに対しても少し制限を設けることにする。ここでいうプログラムは、CやJavaなどの命令型言語で書かれたものとする。しかし、このプログラムはいわゆる内部状態を持たないものとする。通常、内部状態をグローバル変数で持たせることが多いがそのようなものが定義されていないものとして考えることにしよう。また、プログラムを構成するサブルーチンはその出力は内部入力だけによって決まるものと考える。即ち、純粋な関数になっているとする。このようにすると、コンピュータにアクセスした人のログを取るようなプログラムは作れないのではと直感的に想像されるかもしれないが、そのようなことはない。これは再帰的な呼び出しを用いることで可能となる。詳しく知りたい人はMilewskiの記事を参照するとよい。

そこで、二つのプログラムを繋げるときは次のように考える。二つのプログラムを\(f,g\)とし、その入出力は次のようになっているとする。

f :: a -> m b
g :: b -> m c

二つのプログラムが合成した様子を下図に示す。
f:id:bitterharvest:20170805091209p:plain

プログラム\(f\)を実行した後でその結果に対して\(g\)を実行したとする。プログラムの合成\(>=>\)をHaskellでの型シグネチャは次のように表すことができる。

(>=>) :: (a -> m b) -> (b -> m c) -> m c 

圏論では関数の合成のほかに恒等射が重要な役割を果たす。そこで、恒等射は与えられた値をそのまま返す関数である。プログラムの世界ではコンピュータの世界の値を人間の世界での値にして返す関数になるので、この関数を\(return\)としよう。Haskellでの型シグネチャは次のようになる。

return :: a -> m a 

このように定めると、関数の合成と恒等射は圏論とプログラムでは次のように対応している。

機能 圏論 プログラム
関数合成 \(g\circ f\) \(f>=>g\)
恒等射 \(id\) \(return\)

さて、これまでプログラムということで説明してきたが、関数の合成を\(f>=>g\)で定義し、恒等射を\(return\)で定義したとき、単位律と結合律が成り立っていれば、これは圏となる。このような圏をクライスリ圏(Kleisli category)と呼ぶ。そして、\(>=>\)はフィッシュ・オペレータ(fish operator)と呼べれる。

フィッシュ・オペレータを自分の力で定義できれば、モナドについての説明は終わりである。次回は確認したい方のために、フィッシュ・オペレータを定義する。