What are the functional data structures?
A functional data structure is something that is not imperative and yes, implemented in a functional way. what do I mean by that is, Functional data structures do not use any imperative features like there will be no updates and modifications, and no such operations on a data structure that have any side effects as In functional programming we hardly deal with assignments, and any state modifications on objects.
Now what properties these data structures have?
A functional data structure is always Immutable and Persistent.
In Java, we have mutable data structures that are present in the collection API. like if we look at their methods, many of them have void return types- which indeed means that it’s mutating the state of the passed object rather than creating a new one.
interface Collection<E> {
// removes all element from this collection
void clear();
// returns true if this collection changed as a result of call
boolean add(E e);
}
So these mutable collections aren’t thread-safe, they gets updated by changing the value of particular fields and leave the rest intact.
Functional programs do not allow that partial assignment. They are meant to be immutable.. though we may also get immutable collections from the classic collection itself like,
Set set = Collections.unmodifiableSet(someSet);
So, Collections has unmodifiableSet, list and many more functions that return an unmodifiable view of the collection.
But that’s not enough as, if the older collection gets exposed to anyone, one still can update or modify that collection in place and even if you are left only with the unmodified collection, still you need to update it.
because collections are meant to store and update elements to achieve this you have to copy the elements in the new collection and that is very expensive.
so the very first property that functional data structure is Immutability.
The next property of functional data structure is Persistency, By the term persistent data structure, we mean- whenever any modification occurs in the data structure, we have to preserve the previous state.
The idea is we don’t update the data structure in place or we can say any modification on functional data structure does not change the existing version, it actually produces a new version for that.
For example, a linked list having a few nodes. If we need to add a new node at the front, we will just add it at the front and will preserve the previous state too. so this will be a new version of the list.
Note that it doesn’t copy that large chunk of data, This just reuses the old structure and implements the required changes. This makes persistent data structures fast and efficient.
Next is, the methods of functional data structures are referentially transparent. That is we call a function once, catch the value and later can use it anywhere anytime. it won’t be changed throughout the program. simply saying, for some given input the output will always be the same.
Its also the reason why it is more efficient to use functional data structures as with them we don’t need to put any extra locks, synchronization stuff to secure things.
Like when we work in a concurrent environment with mutable data structures, we need to be a bit careful, we need to guard the access many more things like that, but in functional programming, we know nothing gonna happen with our data, nothing can change it.
Now the point comes why is it more difficult to design and implement functional data structures than imperative ones?
There are a couple of reasons for that.
First, the functional programming is strictly against destructive updates, as they can be dangerous if not used correctly.. and as we know imperative data structures rely on assignments in a crucial way.. so it’s quite difficult to find different solutions for functional programs.
Second thing is, the functional data structure has to be persistent. and that is indeed tough. In imperative data structures, we don’t keep any older newer versions of them. Such data structures are called Ephemeral.
But we have to keep every version of them in the case of persistent data structures.
We can implement persistent data structure in both imperative and functional languages though many as imperative programmers may find persistent data structures more complicated and even less efficient, and slow than an ephemeral data structure. as we need to maintain the previous states of data structures at every update.
But that’s not always true. There are many other points why you should prefer a functional data structure over imperative ones.
let’s try implementing the very basic structure, List in our next blog.