http://d.hatena.ne.jp/propella/20070713/p1 で書ききれなかった続きです。この日記の内容はたぶん全て Squeak 版 Joy でも実行出来ます。http://languagegame.org/pub/Joy.cs
LIST 函手とその自然変換
ここからいよいよ圏論の話になるそうですが、ようするにリスト操作の話です。リスト操作の代表としてはやはり map です。map を使うと、次のように沢山の値を一度に操作できます。この例では、1、2、3、という引数それぞれに double (二倍する)という操作を行います。
- [1 2 3] [double] map == [ 2 4 6 ]
map 関数の面白い所は、もともと数字に作用する double という関数が、map との合わせ技によってリストに作用する関数になってしまう所です。このような合わせ技はいつでも出来るわけではなく。例えば文字列のリストに [double] map させる事は出来ません。「数字」の double が可能だからこそ「数字のリスト」の map も可能なのです。このような数字と数字のリスト、数字のリストの関数の関係を次のように考えます。
- 数字 -> あるパワー -> 数字のリストになる。
- double -> あるパワー -> 数字のリスト用 double になる。
こう言うあるパワーの事を函手(functor)と呼びます(と、こんな説明で良いのだろうか。。。)。ドキュメントでは、リスト用の物を作るあるパワーを LIST(m) と書いています。数字のリストは LIST(数字) で、リスト用 double は LIST(double) です。Joy には型が無いので LIST(数字)に当たる物は無いですが、LIST(double) は [double] map と書けます。
さて、函手 F と G があって、どんな射(morphism: たぶん後述) m と F の値 x に対しても次の関係が成り立つ時、n を F から G のを自然変換 (natural transformations) と言うらしいです。
- n(F(m)(x)) = G(m)(n(x))
抽象的すぎて難しいので例です。最初は単純な例として F も G も両方じ「リストにするパワー」だとします。m は double のような関数で、x は何かのリストです。自然変換の例としては reverse (リスト反転) があります。普通記法で書くと、
- reverse(map(f,L)) = map(f,reverse(L))
あるリストを map してから反転するのと、反転してから map するのでは結果は必ず同じになります。Joy 記法で書くと次のようになります。
- [reverse] dip map == map reverse
- 例: [1 2 3] [double] [reverse] dip map == [ 6 4 2 ]
- 例: [1 2 3] [double] map reverse == [ 6 4 2 ]
プログラミング言語では、自然変換の事を polymorphic と呼びます。ここでも、Joy 記法の素晴らしさが目を引きます。reverse(map(f,L)) を見ても、f とか L とか余計な物があってなんじゃこりゃー！という感じですが、[reverse] dip map だと、すっきり、ああ、ここにあるやつを reverse して map するのだと素直に読めます。[] や dip は「Joy脳」になると次第に見えなくなるから大丈夫です。素人のうちは dip を展開して考えてください。例えばスタックのトップを f とおくと以下のようにすっきりします。
- reverse f map == f map reverse
いくつか Joy 記法と普通記法で自然変換の例を書きます。
- [first] dip i == map first
- 例: [1 2 3] [double] [first] dip i
- 普通記法: f(first(L)) = first(map(f,L))
- ある関数をリストの先頭に適用するのと、リスト全体に関数を適用した先頭は同じ。
- [concat] dip map == [map] cons app2 concat
- 例: [1] [2 3] [double] [map] cons app2 concat
- map(f,concat(L1,L2)) = concat(map(f,L1),map(f,L2))
- リストをくっつけて map するのと、map してくっつけるのは同じ
- この例は難しいので Squeak 版 Joy で一要素ずつ入力して試してみる事をお勧めします。
以下同じような話が続くので省略。
そのほかの函手と自然変換
Set の例は未実装なので省略します。他の函手の例として、リストのリストを挙げます。例えば [[1 2 3][4 5]] な感じです。リスト内の数値を全部二倍する事を考えます。map の方もネストすれば良いです。
- [ [1 2 3][4 5] ] [ [double] map] map == [ [1 4 9][16 25] ]
このままだと map の引数が内側クォートの中に入ってしまっているので外のスタックに出すとこんな風になります。
執筆中。
