I learned that expressions are left associative while abstraction are right associative, however, while solving some examples i faced this problem. Succ 3 Succ 2 when i applied left associativety i got (Succ 3) Succ) 2 which was extremely long to solve. However, i saw this guy on the internet, he said that we should parse it as Succ (3 Succ 2) which is Succ ( Succ Succ Succ 2) and the result is 6. AND THE ANSWER IS RIGHT! So now i am confused, during execution, should use the left or the right rule??

  • 1
    $\begingroup$ Application is left-associative (see e.g. en.wikipedia.org/wiki/…). Succ ( Succ Succ Succ 2) expansion can't possibly be correct since it doesn't follow any associativity rule, be it left or right. I also don't understand why ((Succ 3) Succ) 2 is extremely long to solve. 6 is indeed the correct answer. $\endgroup$
    – user114966
    Mar 12, 2021 at 0:55
  • $\begingroup$ so maybe it's not "extremely" long , but it's essential that i know the definition to solve it, unfortunately our test doesn't include a cheat sheet , so i don't think it's meant to be solved the conventional way. Do you know of any fast way i can solve this without using the definitions ? lambdacalc.io this solver solved it in 49 steps which is unreasonably long for an MCQ question , that's why i said it was long $\endgroup$
    – user28324
    Mar 12, 2021 at 8:17
  • $\begingroup$ This can be solved in 2 steps, by definition of Succ and definition of what you get after simplifying Succ 3. $\endgroup$
    – user114966
    Mar 12, 2021 at 13:43


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.