Functional programming: how far should immutability go? [closed]

Question

I realise that this is probably quite a subjective question, but I'm looking for some insights from those more experienced than I am in functional programming.

It's my understanding that the main motivators for keeping everything immutable are making things easier to understand, and stopping errors from creeping into parallel tasks. The downside to this is that every time you want to make a change to a data structure, you have to copy the whole data structure into a fresh object, but with the desired change. Presumably there is some performance cost to doing this: while I wouldn't think twice about doing that for a small object, surely that becomes incredibly slow if you're working on large matrices or tensors, or similarly large data structures?

In short:

1. Is there a performance penalty for copying immutable data structures, and how significant is it?
2. If so, can you give an example of where you (personally) would draw the line between making something immutable and making it mutable?

Answer 1

It's my understanding that the main motivators for keeping everything immutable are making things easier to understand, and stopping errors from creeping into parallel tasks.

This can be the main motivation. But there are other advantages. But it can result in performance boosts. For instance lockfree and waitfree datastructures are a way to handle parallel processing and aims to reduce the overhead of locking.

The downside to this is that every time you want to make a change to a data structure, you have to copy the whole data structure into a fresh object, but with the desired change.

This is incorrect. You do not need to copy the entire data structure. For instance a finger tree is a typical datastructure in functional programming. It performs insertion in O(d) (with d) the depth of the tree. So it has exactly the same performance.

Working with immutable objects can in many/most cases result in the same time complexity, although the algorithms are usually written differently (for instance lists are usually linked lists and therefore list processing is usually done with the aim to avoid random index lookups).

Furthermore the fact that datastructures are immutable can also result in an efficiency boost. For instance in many programming languages, strings are immutable objects. Some programming languages have a string store that implements a flyweight pattern. If you construct a new string, it checks if the string already exists, and if that is the case, you obtain a pointer to that string. The advantage is that the memory footprint is reduced, and furthermore it can also result in a performance boost, due to the fact that these objects can be cached.

would draw the line between making something immutable and making it mutable?

There are programming languages like Haskell where everything is immutable. In that case mutability is done by using monads, and thus passing new versions of objects through the process. Haskell compilers tend to do a good job and sometimes achieve the same speed as the imperative counterparts.

Answer 2

In languages that make extensive use of immutability, there's the opportunity to use "shortcuts" when copying. The copy and the original can share the same structure since you know they can't change out from under you, because they're immutable. Only the altered part needs to be created.

From the Clojure Docs on their structures:

All of the Clojure collections are immutable and persistent. In particular, the Clojure collections support efficient creation of 'modified' versions, by utilizing structural sharing, and make all of their performance bound guarantees for persistent use.

(Emphasis mine)

Basically, if you have a list

[0 1 2]

And you conjoin (add) to it

(conj [0 1 2] 3)

This creates a copy with a 3 added to the end. Because the original and the copy share the first 3 elements however, the entire list didn't need to be copied. The "copy" references the common parts of the original structure, and the 3.

And where do you draw the line? UI is proving difficult to only use immutable objects for. I've pretty much given up on entirely avoiding mutability in this domain. The key is to limit it to only where it's necessary. 99% of the functions should embrace immutability, then have the 1% that deals with the messy bits (like UI callback code) tucked away somewhere. That's a learned line though, and difficult to properly communicate.

When in doubt, make it immutable.