Why do we use persistent data structures in functional programming?

Question

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?

Answer 1

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.

Answer 2

It is easier to correctly work with persistent data structures than it is to work with mutable data structures. This, I would say, is the main advantage.

Of course, theoretically speaking, anything we do with persistent data structures we can also do with mutable ones, and vice versa. In many cases persitent data structures incure extra costs, usually because parts of them have to be copied. These considerations would have made persistent data structures much less attractive 30 years ago when supercomputers had less memory than your mobile phone. But nowadays the main bottlenecks in production of software seem to be development time and maintainance costs. Thus we are willing to sacrifice some efficiency in execution for efficiency in development.

Why is it easer to use persistent data structures? Because humans are really bad at tracking aliasing and other kinds of unexpected interactions between different parts of a program. They automatically think that because two things are called x and y, then have nothing in commmon. Afer all, it takes effort to figure out that "the morning star" and "the evening star" are really the same thing. Similarly, it is very easy to forget that a data structure may change because other threads are working with it, or because we called a method which happens to change the data structure, etc. Many of these concerns are just not present when we work with persistent data structures.

Persistent data structures also have other, technical advantages. It is typically easier to optimize them. For example, you're always free to copy a persistent data structure onto some other node in your cloud if you wish, there is no worry of synchronization.

Answer 3

Adding to others' answers, and reinforcing a mathematical approach, functional programming also has a nice synergy with Relational Algebra, and Galois Connections.

This is extremely useful in the area of Formal Methods.
For instance:

• Formal proofs in program verification are simplified with Extended Static Checking;
• A number of properties from Relational Algebra are useful in SAT solving, with tools such as Alloy;
• Galois Connections allow a calculational approach to software specification, as seen in this blog, with a reference to a paper, by Shin-Cheng Mu and José Nuno Oliveira.
• Galois Connections (and Functional Programming) can be used in a Design by Contract fashion, since they are a more general concept than Hoare Logic.

Example

The Hoare triple $\{p\} P \{q\}$ can be expressed as the contract $[P] \cdot \phi_p \subseteq \phi_q \cdot [P]$, where

• $[P]$ is the relation that denotes the semantics of program $P$;
• $\phi_p$ (resp. $\phi_q)$ denotes the coreflexive relation that captures predicate $p$ (resp. $q$);

This approach also allows weakest pre-condition and strongest post-condition calculation, which comes in handy in a number of situations.