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

[Steven D'Aprano]

On Tue, Dec 30, 2014 at 09:41:33PM -0800, Alex Kleider wrote:

> In the process of doing so I discovered that list multiplication does 
> not at all behave the way I expected (as demonstrated by the 
> 'bad_flip_2_D' function.)

Well, don't keep us in suspense. How did you expect it to behave, and 
how does it actually behave?

My guess is that you expected this:

py> grid = [[0]*5]*4   # make a 4x5 grid
py> print(grid)
[[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]

Looks good so far! But:

py> grid[1][1] = 99  # Adjust a single cell.
py> print(grid)
[[0, 99, 0, 0, 0], [0, 99, 0, 0, 0], [0, 99, 0, 0, 0], [0, 99, 0, 0, 0]]

while you expected:

[[0, 0, 0, 0, 0], [0, 99, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]


Am I right?


The problem is that you guessed that list multiplication *copies* the 
items. It does not. It just repeats them. So:

    [a, b]*3

returns 

    [a, b, a, b, a, b]

but NOT 

    [copy(a), copy(b), copy(a), copy(b), copy(a), copy(b)]

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.

Aside: the copy module actually implements copying for some immutable 
objects by returning the original!

py> import copy
py> x = 2.3456
py> y = copy.copy(x)
py> y is x
True
py> x = []
py> y = copy.copy(x)
py> y is x
False

Floats are immutable and cannot be modified, so there is nothing you can 
do to change float x. Making an actual copy is a waste of time, so 
copy.copy just returns the same float object. But lists are mutable and 
can be modified, so copy.copy has to actually build a new list.

But I digress. Back to list multiplication.

Since list multiplication doesn't *copy* the items, it just repeats 
them, we can see what is happening if we expand the code a little with a 
temporary variable:

Before:

grid = [[0]*5]*4   # make a 4x5 grid
grid[1][1] = 99  # Adjust a single cell.


Expanded:

x = [0]*5  # Make a single list of five immutable integers.
grid = [x]*4  # Like [x, x, x, x]

So here we have a list of four references to the same list, not four 
different lists! If you change any one of those references, or indeed 
the original "x" reference *in-place*, they all change. They all change 
because in fact there is no "all", there is only one!

grid[1][1] = 99
print(x)
-> prints [0, 99, 0, 0, 0]


The solution to this is not to use list multiplication unless you know 
the items are immutable. Instead, a list comprehension solves the 
problem nicely:

py> grid = [[0]*5 for i in range(4)]
py> grid[1][1] = 99
py> print(grid)
[[0, 0, 0, 0, 0], [0, 99, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]



-- 
Steven