Functional Data Structure

Lets start with something that we already know or have experienced in java or any imperative language with imperative data structures.
Imperative data structure(ephemeral data structures) are mutable in nature, In our day to day usage of data structures in java we mutate lists, arrays and other data structure to implement algorithms.

When we talk about functional programming language the most buzz word is immutability. In functional programming languages the data structures are immutable (So what happens to all the update operations?)

Update operations on such data structure that changes the value of data structure creates a new instance of data structure. So after performing x updates on data structure you’ll have all pervious versions of data structure available for you to access. This ability of data structure to keep all the previous versions after updates is called Persistent data structure. Where in Ephemeral data structures every update destroys its previous state.

Functional paradigm doesn’t support destructive updates, the existing data structure is not updated but instead a new data structure is created with the updated value. hence keeping both new and old version of data structure after update. (Does that mean we end up with extra copy of data??)
Surprisingly the answer is NO. Functional data structure use the concept of data sharing

Sharing of immutable data often lets us implement functions more efficiently;we can always return immutable data structures without having to worry about subsequentcode modifying our data. There’s no need to pessimistically make copies toavoid modification or corruption

Lets take an example of linked list
xs = [2,3]

xs = 1 ++ xs

When we add an element 1 to the front ofan existing list xs [2,3], we return a new list, in this case (1,xs). Since lists areimmutable, we don’t need to actually copy xs; we can just reuse it. This is called datasharing.

There’s no real removing going on. The originallist, xs, is still available, unharmed. We say that functional data structures arepersistent, meaning that existing references are never changed by operations on thedata structure.
I hope this justifies the answer NO for having extra copy of data while performing operation on immutable data structure.

Lets take an example of Singly Linked list from wikipedia to understand this conceptConsider two Lists xs and ys
xs  =  [0, 1, 2]

ys  =  [3, 4, 5]
                                                

Lets create a new linked list zs concatenating two lists xs and ys
          zs = xs ++ ys

Notice that the nodes in list  have been copied, but the nodes in  are shared. As a result, the original lists ( and ) persist and have not been modified.

The reason for the copy is that the last node in  (the node containing the original value ) cannot be modified to point to the start of , because that would change the value of .

Immutable classes are easier to design, implement, and use than mutable classes. They are less prone to error and are more secure.
Immutable objects are inherently thread-safe; they require no synchronization. They cannot be corrupted by multiple threads accessing them concurrently.This is far and away the easiest approach to achieving thread safety. In fact, no thread can ever observe any effect of another thread on an immutable object.Therefore, immutable objects can be shared freely.

A consequence of the fact that immutable objects can be shared freely is that you never have to make defensive copies because the copies would always be same as the original objects.You don’t have to provide clone or copy method for Immutable class unlike String class in Java which does have a copy constructor.

There are some classes for which immutability is impractical. If a class cannot be made immutable, limit its mutability as much as possible. Reducing the number of states in which an object can exist makes it easier to reason about the object and reduces the likelihood of errors.