Why do we use persistent data structures in functional programming?

Problem Detail: 

Functional programming employs persistent data structures and immutable objects. My question is why is it crucial to have such data structures here? I want to understand at a low level what would happen if the data structure is not persistent? Would the program crash more often?

Asked By : gpuguy

Answered By : Uday Reddy

When you work with immutable data objects, functions have the property that every time you call them with the same inputs, they produce the same outputs. This makes it easier to conceptualize computations and get them right. It also makes them easier to test.

That is just a start. Since mathematics has long worked with functions, there are plenty of reasoning techniques that we can borrow from mathematics, and use them for rigorous reasoning about programs. The most important advantage from my point of view is that the type systems for functional programs are well-developed. So, if you make a mistake somewhere, the chances are very high that it will show up as a type mismatch. So, typed functional programs tend to be a lot more reliable than imperative programs.

When you work with mutable data objects, in contrast, you first have the cognitive load of remembering and managing the multiple states that the object goes through during a computation. You have to take care to do things in the right order, making sure that all the properties you need for a particular step are satisfied at that point. It is easy to make mistakes, and the type systems are not powerful enough to catch those mistakes.

Mathematics never worked with mutable data objects. So, there are no reasoning techniques we can borrow from them. There are plenty of our own techniques developed in Computer Science, especially Floyd-Hoare Logic. However, these are more challenging to master than standard mathematical techniques, most students can't handle them, and so they rarely get taught.

For a quick overview of how the two paradigms differ, you might consult the first few handouts of my lecture notes on Principles of Programming Languages.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/10002