昨日のエントリー「Haskell の構文に惑わされているね」を少し引っ張るんだけど; Haskellの関数定義/呼び出し*1構文は、誤解や混乱を招く危険もあるにはあるけど、やっぱり巧みに出来ているなー。誤解したまま使ってもツジツマがあうところが素晴らしい。
その誤解とは、f x y のような書き方を2引数(2変数)関数だと思うこと。昨日の例 g a b x = a*x + b を使うけど、絵の描きやすさの都合から、a*x + b を b + a*x の形に書きますね。
g b a x = b + a*x
これは、次の図1のように思っても問題ありません。
図1
g とは、b a x
| \ /
\ *
\ /
+
|
けど、より精密に描けば(アスキー絵では無理)
図2
掛け算のところから説明すると; a*x という算術の式は、(*) a x のことです。(*)の正体は λs.λt.(mult(s, t)) です。multはリアルな(例えば機械でサポートされた)掛け算関数。よって、(*) a x をハッキリと書けば、
- (λs.λt.(mult(s, t)))・a・x
これが図2の右上の部分です。左下の足し算のところは、
- (λs.λt.(add(s, t)))・b・y
これらをつなげると、b + a*x という算術式は
- (λs.λt.(add(s, t)))・b・((λs.λt.(mult(s, t)))・a・x)
だいぶ煩雑ですから再び (+), (*) を使えば、
- (+)・b・((*)・a・x)
式のなかにドット「・」(Haskellでは空白)が4つ出現しますが、それは図2のバブル(適用に相当するオダンゴ印)が4個あることに対応します。
g1 b a = (.) (b+) (a*) も絵に描いてみましょうか。
まず、反図式順で関数合成*2するコンビネータは λg.λf.λx.g・(f・x) だけど、内側の λx.g・(f・x) はこんな感じ。
図3
この図のf, gのところに、(b+)と(a*)を“代入”すると、(.) (b+) (a*) となりますよね。(.) (b+) (a*) を一気に描いてしまうと:
図4
実はこの絵、バブル(適用に相当するオダンゴ印)を描き忘れているところがあります。それと、上のほうの変数xは消してもいいです。ラムダ束縛された後の変数名は残す必要はありませんから(残しても別にいいけど)。
さて、赤で囲ってある部分を見てください。右の赤囲みが λt.((*)・a・t) = (a*)、左の赤囲みが λt.((+)・b・t) = (b+) です。(a*)と(b+)のなかにパラメータ(自由変数)a, bがあるので、そのパラメータのワイヤーが上に伸びます。
ここで、先の図2の g b a x と図4の g1 b a をよーく見比べてください。図4には、金槌で叩かれて腫れ上がった小指のようなものが2つありますね。これはラムダ抽象により出来たカーブです。この赤く塗ったカーブがなくなれば、図2 g b a x をxでラムダ抽象したものと、図4 g1 b a はまったく同じです。
腫れ上がった小指に関しては次の図5を見てください。こういう形のカーブ(赤いところ)は消えてしまうのです。
図5
右側の紐を下に引っ張って赤く塗ったカーブを消滅させる変換がイータ(η)変換です。式で書くなら:
- λx.(f・x) ⇒ f
このイータ変換は単なる記号的変型に思えますが、背景となるリアルな計算法則があります。それは、f:X→ZY だとして、
- Λ<x, y| E(f(x), y)> = f
です。この法則は、Γ(f) = <x, y| E(f(x), y)> とすると、Γ(大文字ガンマ)が定義するオペレータ(関数を加工する操作)が、ラムダ抽象のオペレータΛのちょうど逆になることを主張しています。Γは、リアルワールドでのuncurryです。
時間があるときに、オダンゴを描いて考えてみてください。Haskell構文に関して、別な側面からの理解ができるでしょう。