[Tutor] Making Doubly Linked List with Less Lines of Code.

[Steven D'Aprano]

On Fri, Jan 02, 2015 at 09:57:29AM -0800, Alex Kleider wrote:
> On 2015-01-01 17:35, Alan Gauld wrote:
> 
> >Repeats replicates the reference to the object but
> >does not create a new object.
> 
> This part I can understand but, as Steven has pointed out,
> this behaviour changes if the object being repeated is immutable.
> Why would one get a new object (rather than a new reference to it)
> just because it is immutable?  It's this difference in behaviour
> that depends on mutability that I still don't understand even though
> Steven did try to explain it to me:
> """
> If the list items are immutable, like ints or strings, the difference
> doesn't matter. You can't modify immutable objects in-place, so you
> never notice any difference between copying them or not.
> """

No, you misunderstood what I was trying to say.

Let's create a list with one mutable and one immutable object, then 
double it:

py> a = [{}, 999]
py> b = a*3
py> print(b)
[{}, 999, {}, 999, {}, 999]

The list b has 6 items, but only two different objects inside b: there 
is a dict, repeated three times, and an int, repeated three times. We 
can check this by printing the IDs of each item:

py> print([hex(id(x)) for x in b])
['0xb7bf1aec', '0xb7b6c580', '0xb7bf1aec', '0xb7b6c580', '0xb7bf1aec', '0xb7b6c580']

If you study them carefully, you will see only two distinct IDs:

'0xb7bf1aec', '0xb7b6c580'

The exact values you get will differ, of course. On some versions of 
Python, you might see something like:

['0x1', '0x2', '0x1', '0x2','0x1', '0x2']

depending on what values the compiler uses for the IDs. But the 
important thing is there are only two of them. We can let Python check 
for duplicates by using a set:

py> print(set([hex(id(x)) for x in b]))
{'0xb7b6c580', '0xb7bf1aec'}

Go back to our list b. Naturally, we can modify *the list* directly:

py> b[2] = {'a': 1}
py> b[3] = 23
py> print(b)
[{}, 999, {'a': 1}, 23, {}, 999]

Notice that when we assign to a list item, it replaces whatever 
assignment was there: position 2 used to refer to an empty dict, now it 
refers to a different dict; position 3 used to refer to an int, now it 
refers to a different int. We can change the list, because lists are 
mutable.

We can change dicts *in place* too:

py> b[0]['c'] = 3
py> print(b)
[{'c': 3}, 999, {'a': 1}, 23, {'c': 3}, 999]

Because we have modified the dict object, not re-assigned it, the change 
shows up in both position 0 and position 4. It doesn't show up in 
position 2, because it is a different dict there now.

But there is no way to change ints in place! Because they are immutable, 
there's nothing we can do to change that int 999 into a different value. 
It will always be 999. The only way to change an int is to replace it 
with a different object, and we've seen that the way to do that in 
Python is by assigning to the list index. Even something that at first 
glance looks like "increment" is actually "add 1 and re-assign":

py> b[1] += 1
py> print(b)
[{'c': 3}, 1000, {'a': 1}, 23, {'c': 3}, 999]
py> print([hex(id(x)) for x in b])
['0xb7bf1aec', '0xb7b6c600', '0xb7afb70c', '0x823c160', '0xb7bf1aec', '0xb7b6c580']


Now there are five distinct IDs.

With mutable objects, identity can be important. There is a difference 
between:

a = []
b = []

and

a = []
b = a

In the first case, a and b are distinct lists. In the second case, a and 
b are the same list.

But with immutable objects, there is nothing you can do (except check 
the IDs) that will reveal the difference between having one or two 
distinct objects:

a = 123
b = 123

*may or may not* set a and b to distinct objects. Because when it comes 
to immutable objects, it makes no difference.


-- 
Steven