Functional programming: how far should immutability go?

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.

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.

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 not quite true. If your data structure consists of multiple nodes (linked with e.g. pointers), you only need to copy the path from the changed part up to the root.

E.g. consider this binary tree:

    |
    a
   / \
  b   c
 / \ / \
d  e f  g

If you want to change a value in node c, you only have to create modified copies of a and c:

    |
    a'
   / \
  b   c'
 / \ / \
d  e f  g

The rest of the structure can be reused. The unchanged nodes are shared between different versions of the tree. This sharing is safe precisely because of immutability.