左結合と右結合 | Chandler@Berlin

Chandler@Berlin

ベルリン在住

English version

λ式では函数の適用は左結合という規則を忘れていたので追加しておこう.これは

f x y = (f x) y

と書くが,まあ,左側から処理するということで良いだろう.たとえば,λ式ではないが,1 - 2 - 3 は,左結合であり,(1 - 2) - 3 となる.(括弧のある方が先に計算される) したがって,

1-2-3 = (1-2)-3
= -1-3
= -4

である.これが右結合であれば,

1-2-3 = 1-(2-3)
= 1-(-1)
= 2

となって答えが異なる.λ式で書けば,

λx. λy. λz. x - y - z

に 1 2 3 を適用すると,

x. λy. λz. x - y - z) 1 2 3 ... x に 1 を適用
= (λy. λz. 1 - y - z) 2 3 ... y に 2 を適用
= (λz. 1 - 2 - z) 3
= (λz. -1 - z) 3 ... z に 3 を適用
= -1 - 3
= -4

ということになる.左結合ならば x = 1,y = 2, z = 3 であって,右結合ならば x = 3,y = 2, z = 1 であり,何も言わなければ左結合となる.