What is the difference of λx. x (λy. y) and (λx. x) (λy. y)

Lambda expressions extend as far to the right as possible. For example λx. x λy. y is the same as λx. x (λy. y), and is not the same as (λx. x) (λy. y).

I cant see the difference, in both cases it seems that (λy. y) is applied to (λx. x) reducing to (λy. y), isnt this the case?

What is the reduction of the first case so?

Solution

I cant see the difference, in both cases it seems that (λy. y) is applied to (λx. x) reducing to (λy. y), isnt this the case?

I think you meant to write "(λx. x) is applied to (λy. y)", rather than the reverse. (We say that a function is "applied" to its argument, not the other way around.)

But to answer your question — no. The formula λx.x λy.y means λx.x(λy.y), which means λx.(x(λy.y)); that is, it's a function that takes a parameter x (which is a function), applies that parameter to the identity function λy.y, and returns the result.

I see that you know Python, so in Python terms:

Let identity be the function defined as
```
def identity(y):
    return y
```
Then λy.y means identity.
λx.x(λy.y) means
```
lambda x: x(identity)
```
So, for example, (λx.x(λy.y))(λt.3) is
```
(lambda x: x(identity))(lambda t: 3)
```
which evaluates to 3.
(λx.x)(λy.y) means
```
identity(identity)
```
which, as you say, reduces to just identity; so ((λx.x)(λy.y))(λt.3) is
```
(identity(identity))(lambda t: 3)
```
which evaluates to (lambda t: 3).
λx.x λy.y means λx.x(λy.y), not (λx.x)(λy.y).