2009-03-23

left-associative and right-associative

Japanese version

I forget to explain one rule that function application is ``left-associative.''

f x y = (f x) y,

The function is processed from left to right. For example, 1 - 2 - 3 is not a λ expression, but it is a left-associative example , means (1 - 2) - 3. Enclosed by parentheses '()' is calculated first. Therefore,

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

If this is right-associative,

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

Please note the answer is different. If we write this function as a λ expression,

(λx. λy. λz. x - y - z) 1 2 3

This concludes

x. λy. λz. x - y - z) 1 2 3 ... apply x to 1
= (λy. λz. 1 - y - z) 2 3 ... apply y to 2
= (λ z. 1 - 2 - z) 3
= (λz. -1 - z) 3 ... apply z to 3
= -1 - 3
= -4.

x = 1, y = 2, and z = 3 if this is left-associative and x = 3, y = 2, and z = 1 if this is right-associative. We use left-associative in λ calculus unless it is explicitly mentioned.

No comments: