Inner-mosts Lists in Python

Question

Why? Look they are equal, initially. You do the same operation but hey you get different structures. Why do the two methods of constructing nested lists give different results?

>>> lll=[[[[[]]*2 for a in xrange(2)] for b in xrange(2)]]
>>> ll=[[[[[]]*2]*2]*2]
>>> lll
[[[[[], []], [[], []]], [[[], []], [[], []]]]]
>>> ll
[[[[[], []], [[], []]], [[[], []], [[], []]]]]
>>> ll==lll
True
>>> ll[0][0][0][0]=1
>>> lll[0][0][0][0]=1
>>> ll==lll
False           #Why?

Structure

This question about mutable types has been answered sooooo many times. Please use the search bar — JBernardo, Oct 06 '11 at 15:35
@JBernardo: which question? If it is so simple thing, go on and answer. I cannot see straight away the link between mutability and thi s question. — hhh, Oct 06 '11 at 15:35
You're multiplying lists (mutable objects) thus creating lots of references to the same object. At first they will look like the other version, but when you add an element, all of them will have the element. THIS has been answered many many many times. — JBernardo, Oct 06 '11 at 15:45
@JBernardo: if so many-many times, can you post a dup? I will happily vote to close if there is really duplicates about this. — hhh, Oct 06 '11 at 15:48
Not a duplicate of this specific question (some gibberish with tons of lists inside each others). Just search for one of the hundreds of questions about list multiplication — JBernardo, Oct 06 '11 at 15:56

NPE · Answer 1 · 2011-10-06T14:53:35.843

Well, ll and lll don't compare equal because they contain different values:

In [3]: ll[0][0][0][0]=1

In [4]: lll[0][0][0][0]=1

In [5]: ll
Out[5]: [[[[1, []], [1, []]], [[1, []], [1, []]]]]

In [6]: lll
Out[6]: [[[[1, []], [[], []]], [[[], []], [[], []]]]]

Now, let's step back and take a simpler example (all these brackets make my head spin):

In [20]: a = [[0]]*2

In [21]: b = [[0] for _ in range(2)]

In [22]: a
Out[22]: [[0], [0]]

In [23]: b
Out[23]: [[0], [0]]

In [24]: a[0][0] = 1

In [25]: b[0][0] = 1

In [26]: a
Out[26]: [[1], [1]]

In [27]: b
Out[27]: [[1], [0]]

The reason this is happening is that both elements of a point to the same list, whereas the two elements of b point to two different lists:

In [29]: id(a[0]), id(a[1])
Out[29]: (14760488, 14760488)

In [30]: id(b[0]), id(b[1])
Out[30]: (14761136, 14760704)

agf · Accepted Answer · 2011-10-06T15:19:04.833

When you use list comprehensions like that, new lists are created for each iteration.

When you multiply a list, the same reference is duplicated over and over.

When that reference is to a list, it means that the same inner list is duplicated over and over.

So, when you multiply, there is only one empty list, referenced twice by a single list, which is referenced twice by a single list, which is referenced twice by another single list, which is the only item in the final, outer list.

When you use a list comprehension, each reference is to a new, different list.

So, when you point the first item of the list containing two references to the empty list to a different object, you see the change everywhere that list is referenced. Since it's referenced twice by a list that is itself referenced twice, you see the change in four places.

If you were to append a value to the very inner list:

ll[0][0][0][0].append(1)

You'd see that value referenced eight times:

[[[[[1], [1]], [[1], [1]]], [[[1], [1]], [[1], [1]]]]]

because all the inner lists are actually the same list.

The real structure of ll isn't what it appears to be above, but:

[                   ]
         |
 [       ,         ]
     \       /
     [   ,   ]
       \   /
       [ , ]
        \ /
        []

The way it is displayed by Python is quite misleading.

...this is interesting, ll[0][0][0][0].append(1) and lll[0][0][0][0].append(1) work totally differently. +1 never thought about this, good. There must be more surprising result with this, thingking... — hhh, Oct 06 '11 at 15:10
@hhh The core is that there is only one list at each nesting level, even though there appears to be more as you go deeper, and there are only two references at each nesting level, to the same object. Because of this, you will get weird results for doing anything to any of the inner lists when you use multiplication on nested lists. — agf, Oct 06 '11 at 15:14

score 1 · Answer 3 · answered Oct 06 '11 at 15:25

In Python, object copying is done as shallowly as possible for efficiency reasons, this is why [[0]] * 2 produces a copy of the innermost list.

But list comprehension evaluates the expression each time through the loop, which is why [[0] for _ in range(2)] produces a list of distinct lists the expression in this case is [0], which when evaluated creates a unique instance of a list each time.

Excerpt from Python v2.7.2 docs:

The comprehension consists of a single expression followed by at least one for clause and zero or more for or if clauses. In this case, the elements of the new container are those that would be produced by considering each of the for or if clauses a block, nesting from left to right, and evaluating the expression to produce an element each time the innermost block is reached.

(My own emphasis on the key phrase.)

...never really thought that list-comprehension could be used like this. What a pain to create it without list comprehension or? — hhh, Oct 06 '11 at 15:29
I do explain this briefly at the top of my answer, but good link to the docs. — agf, Oct 06 '11 at 16:48

Inner-mosts Lists in Python

3 Answers3