"there is really no alternative in the general case without imposing huge overhead, making copies of everything "just in case"."
Actually, there is an alternative: use persistent data structures. Granted, it's an alternative that isn't terribly "Pythonic", but an alternative nonetheless.
Seems like a very verbose way to explain the situation to the original poster...
Lists are mutable, strings aren't. When you reassign one of the dictionary values pointing to an existing string, it can't change that string, so it creates a new one. Since lists can be changed, it doesn't need to create a new one and can modify the existing list.
The distinction between mutable and immutable is important,
but more important here is the difference between
>>> dict['a']=3
and
>>> dict['a'].append(3)
The first rebinds dict['a'] (and in the process mutates
the object dict is bound to).
The second mutates the object dict['a'] is bound to (and
in the process binds dict['a'][1] to 3 [EDIT: not really --
1 is not a name and so doesn't have a binding]).
I think looking at it purely in terms of mutable versus
immutable makes it more likely for a newbie to expect the
assignment above to work differently depending on the
mutability of dict['a']'s old or new value. (I have seen
this type of error.)
EDIT 2: I think a better way of making my point is that
this:
> When you reassign one of the dictionary values
> pointing to an existing string, it can't change that
> string, so it creates a new one.
can be taken (incorrectly) to imply that reassigning a
dictionary value pointing to an existing list will mutate
that list.
Actually, there is an alternative: use persistent data structures. Granted, it's an alternative that isn't terribly "Pythonic", but an alternative nonetheless.