コンビネータメモ
メモメモ。
Z
Yをη変換するとZ
Y f = f (Y f) Z f = f (λy.Z f y)
η変換ってなんだかよくわからんけど、λを一個追加(削除?)することらしい。
とりあえずη変換してみよう。
(lambda (x) x) ; ↓ η変換 (lambda (y) ((lambda (x) x) y))
一回lambdaで囲んでも意味は変わらない。
η変換すると、理論上での計算の意味合いは全く一緒だけど、計算機上では評価順序が変わるのがポイントらしい。
不動点オペレータ - ボクノスコレネ。
これが純粋なYコンビネータ。
Y = λf.(λx.f (x x)) (λx.f (x x))
外側は意味が無いので、一番内側の(x x)をaでη変換すると、(λa.(x x) a)。
代入する。
Z = λf.(λx.f (λa.(x x) a)) (λx.f (λa.(x x) a))
おぉ。η変換だったのか。
純粋なYだと、最後の(x x)が評価されて、Yの方だけガンガン進んでしまう。そこで、η変換して計算の順序を遅らせる。Haskellで言うと、(1 +)的な状況を作る。すると、計算できないから、λごと渡す。後で(x x)の中を見る。遅延する。
これが、遅延評価の仕組み。演算全てをη変換すれば、遅延評価系になる。Haskell完成。
ほうほう。理解が深まった気がする。「sk修行は効果てきめんだ」
オメガ
Ω = (λx.x x) (λx.x x)
これは勇気が無くて、試せないな(笑)
YK
アレ?
Y K a = K (Y K) a = Y K
アレ?
((((Y K) 'a) 'a) 'a)
ホントダ。楽しい。
