Evaluating lambda expression

Question

1. $((λfx.f(f(x))) (λy.y^2)$ (1) is finally evaluated to $1^4=1$

2. $(3)(3) (\text{inc})(0)=(27)(\text{inc})(0)=27$

3. Is λfx the same as λf.λx That is is $((λfx.f(f(x))) (λy.y^2) equivalent to $(λf.λx.f(f(x)) (λy.y^2) ?

Is it correct?

Thanks much in advance!

Answer 1

You could have used some functional language interpreter to check this, e.g. Haskell or OCaml, etc.

> let zero f x = x
> let one f x = f x
> let two f x = f (f x)
> let three f x = f (f (f x))
> let inc n f x = f (n f x)
> let test n = n ((+) 1) 0

1. Yes.

   > test (two two one)
   1
   

2. Yes.

   > test (three three inc zero)
   27
   

3. Yes, $\lambda\ f\ x.\ M$ is a short notation for $\lambda f.\ \lambda x.\ M$.

I hope this helps ;-)