Does immutability mean that huge collections get completely recreated every time they change?

Question

I've been trying to get into functional programming lately. Specifically I've been interested in Clojure. I understand most of the arguments for immutability of data, but one thing just doesn't make sense to me. Suppose I have a very large collection like a map or an array containing hundreds of millions of items. If I can't change it, then does that mean that every time I want to add a new item I'm essentially recreating the entire collection? That sounds like a horrible idea. How is a situation like this handled in languages where everything is immutable?

Answer 1

In the case of Clojure, they are not recreated each time. Rich Hickey made sure utilize persistent data structures, as he explains in an "Expert to Expert" interview.

You can think of it more like a linked list.

class LinkedList<E> {
    E data;
    LinkedList<E> next;

    LinkedList<E> cons(E item) {
        return new LinkedList(item, this);
    }
}

Each time you cons a value onto the front, you do not need create a new linked list, but instead you merely keep a reference to the previous.

Similarly, even data structures like maps can be made to share large amounts of their data when they only differ by minor amounts. This helps reduce the size used.

Additionally, Clojure also provides transient data structures, which are mutable versions of its immutable collections, allowing you to make multiple changes to a data structure without the expense of copying/sharing data.