Search code examples
lambda-calculus

How do I do this reduction?


I'm stuck on how to do this reduction, I have read this post and this pdf but I can't seem to find a solution: (λx.yx)((λy.λt.yt)zx)=> (λx.yx)(λt.zxt) => y(λt.zxt)

but the solution should be yx according to online solvers.

could someone explain what passages I am doing wrong? What are the passages that you should follow to do it right?


Solution

  • applicative order

    β y := z

    (λx.yx)((λy.λt.yt)zx) 
              =    =  =
    
    (λx.yx)((λt.zt)x)
    

    β t := x

    (λx.yx)((λt.zt)x)
              =  = =
    
    (λx.yx)(zx)
    

    β x := zx

    (λx.yx)(zx)
      =  = ====
    
    y(zx)