[graue]

> Immutable arrays, where the entire array must be copied with the change of one element, are an example of that.

Only in a naive implementation. Clojure, for example, has a persistent vector that only requires O(log32 n) copying, which grows so slowly as to be effectively O(1).

See: http://hypirion.com/musings/understanding-persistent-vector-...