I try to study more rigorous topics of programming as I realized there are many paradigms out there that I don't know anything about. I followed books like SICP and Foundations of Computer Science etc. I am now studying algorithms in a formal, proof oriented manner. When I was studying Quicksort, I realized that I have no idea how could I implement this in a functional language. It is an in-place sorting algorithm but how can I achieve that without mutation is beyond me.
Maybe there is an easy answer, I don't know many practical and theoretical concepts yet. But I read that functional languages are based on lambda calculus and it is equivalent in power to Turing Machines. And I found an implementation in Haskell but I don't know about monads, hopefully I will learn eventually.
So could you explain how this is possible in as simple terms as possible? Does lambda calculus itself have the notion of mutation? Don't go too harsh on this because I don't know lambda calculus much, just programmed in Scheme. A yes or no answer with a little explanation would be enough.
Does lambda calculus itself have the notion of mutation?
No, there is no notion of mutation. You simply have functions application (apply) and function abstraction (lambda).