Iコンビネータ - mrsekut-p

Iコンビネータ

identity combinator

$ \lambda x.x

恒等関数

Haskellではid

IコンビネータはSコンビネータとKコンビネータの組み合わせで表現できる

SKKコンビネータ

と表記することが多いが、2つ目のKは何でもいい

SKSでもSK(KK)でもなんでもいい

SK_やなmrsekut.icon

code:簡約する

SKK

= (λxyz.xz(yz))KK

→ λz.Kz(Kz)

Kz

= (λxy.x)z

→ λy.z

λz.Kz(Kz)

→ λz.(λy.z)(λy.z) // ①

→ λz.z

= I

①から次へ行くときが注意が必要

λz.(λy.z)(_)に実引数xを与えればxが返ってくることが確認できる

code:簡約

(λz.(λy.z)(_))x // zにxを代入

→ (λy.x)(_) // yに(_)を代入

→ x

例

code:hs

k = const

s x y z = x z (y z)

skk :: a -> a

skk = s k k