why are some types immutable?

[Roy Smith]

Torsten Mohr <tmohr at s.netic.de> wrote:
> reading the documentation (and also from a hint from this NG)
> i know now that there are some types that are not mutable.
> 
> But why is it this way?
> 
> From an overhead point of view i think it is not optimal,
> for example for a large string it could be much faster to
> have it changed in place, not generating a new one for
> every step in a change.

There has been a huge amount written about immutable types recently.  A 
search of the Google news archives should turn up tons of articles.

But, in a nutshell, the biggest reason for immutable types (tuples and 
strings) is that this lets they be dictionary keys.  If you want to know 
why dictionary keys have to be immutable, do that google search; there 
was a huge thread on exactly that subject just in the path month or two.

Making strings immutable has some good points (in addition to making 
them usable as dictionary keys) and bad points.  On the good side, it 
lets you intern strings and share memory.  For example:

>>> a = "fred"
>>> b = "fred"
>>> id (a)
3587520
>>> id (b)
3587520

when the interpreter saw the string "fred" in the second assignment 
statement, it looked it up and discovered that it already had a string 
with the value "fred", so it just re-used the same string (which is why 
they both have the same id).  This saves memory (which can become 
important when you have a lot of strings).  It also makes string 
comparison more efficient, since a test for equality can often be 
satisfied by just comparing id's.

The bad side is that, as you mentioned, things like:

s = ""
for c in getCharacters():
   s = s + c

become very inefficient: O(n^2).  Fortunately, there is an easy idiom to 
avoid that quadratic behavior.  You just accumulate the characters in a 
list, O(n), and then convert the list to a string with join(), also 
O(n).  Two O(n) passes is a heck of a lot better than a single O(n^2).

l = []
for c in getCharacters():
   l.append (c)
s = "".join (l)

Other types of in-place string manipulation could use the same trick.