Why in Python a list self-reference doesn't behave the same way when extended or summed?

Question

This is just a theoretical question and doesn't have any use case I believe.

I was playing with lists self reference and I noticed that:

 >>> l = []                                                                                                                                        
 >>> l.append(l)                                                                                                                                   
 >>> l.append(l)                                                                                                                                   
 >>> l                                                                                                                                             
 [[...], [...]]                                                                                                                                     
 >>> l+l                                                                                                                                           
 [[[...], [...]], [[...], [...]], [[...], [...]], [[...], [...]]]

And ok the output seems fine? Then I tried:

 >>> l = []                                                                                                                                        
 >>> l.append(l)                                                                                                                                   
 >>> l.append(l)                                                                                                                                   
 >>> l                                                                                                                                             
 [[...], [...]]                                                                                                                                    
 >>> l.extend(l)                                                                                                                                   
 >>> l                                                                                                                                             
 [[...], [...], [...], [...]]

I thought l+l and l.extend(l) would behave the same way with the only difference that list+list creates a copy

I then checked references but they are all the same:

 >>> l = [] 
 >>> l.append(l) 
 >>> l.append(l) 
 >>> l 
 [[...], [...]] 
 >>> l+l 
 [[[...], [...]], [[...], [...]], [[...], [...]], [[...], [...]]] 
 >>> e =l+l 
 >>> e[0][0] is e[0][1] 
 True 
 >>> e[0][0] is e[0] 
 True 
 >>> e[0] is e[1] 
 True

TLDR Why

>>> l+l                                                                                                                                           
 [[[...], [...]], [[...], [...]], [[...], [...]], [[...], [...]]]

But

 >>> l.extend(l)                                                                                                                                   
 >>> l                                                                                                                                             
 [[...], [...], [...], [...]]

Keeping in mind [extend is the same as +=](https://stackoverflow.com/questions/3653298/concatenating-two-lists-difference-between-and-extend), the answers in [Why does += behave unexpectedly on lists?](https://stackoverflow.com/questions/2347265/why-does-behave-unexpectedly-on-lists) should answer your question. — Guy, Jul 12 '22 at 10:33
Not really or at least I don't get it, I know as I stated that it creates a copy but I still don't get why it's shown with depth 2 rather than 1 like with extend, since the references are all the same except for the outer list obviously. Seems like the implementation of `list+list` takes more space in memory for self-references — Axeltherabbit, Jul 12 '22 at 10:56
check https://stackoverflow.com/q/68261721/13944524. Not exactly the same but related. This is all about representation. "**WHEN** Python figures out that it is the same list" is the key point. — S.B, Jul 12 '22 at 11:29
Yes, I believe the check is done when the self reference is saved in memory, `L.append(L)` does something like `&L(&L)` so it stops because it sees the double L, but `&L(&L)+&L(&L)` creates `&NEWL(&L,&L)` not a nested `L` yet so it keeps going, `&NEWL(&L(&L),&L(&L))` not it stops because there is a looping reference, and this seems to be done in memory not during print — Axeltherabbit, Jul 12 '22 at 13:09

Bharel · Accepted Answer · 2022-07-12T12:19:21.017

3

The recursive __repr__ for builtin objects checks for the first recursion and prints it.

In case of .extend() you take the list of 2 lists, and turn them into a list of 4 lists:

             1
  1.1    1.2    1.3    1.4
[[...], [...], [...], [...]]

Since each list is itself and prints the same, the recursion ends here.

In case of the +, the output object is not the same as the other lists:

                               unique
       1               2               3                4
   1.1    1.2      2.1    2.2      3.1    3.2      4.1    4.2
[[[...], [...]], [[...], [...]], [[...], [...]], [[...], [...]]]

You have one outer list of 4, BUT, each sub list contains 2 items. The recursion only starts when you go into depth 2.

Basically, in the first one 1.1 == 1 but in the second one 1 != unique.

edited Jul 12 '22 at 12:19

answered Jul 12 '22 at 11:24

Bharel

23,672
5
40
80

1

A useful test to demonstrate the difference: `ladd = l + l`, `ladd is l[0]` (`False`), vs. `l.extend(l)`, `l is l[0]` (`True`). (To be clear, I like this answer and up-voted) – ShadowRanger Jul 12 '22 at 11:36
I don't think it has anything to do with `__repr__` but more to do with how it's saved in memory, because if I do `L.extend(L)`, `print( [L] )` I would then aspect the same output as `L+L` right? – Axeltherabbit Jul 12 '22 at 11:51
@Axeltherabbit there's a very big difference. `L.extend(L)` modifies `L`, while `L+L` doesn't modify `L`. `__repr__` checks for recursion once `L` is the same item, and then replaces it with `...`. – Bharel Jul 12 '22 at 12:17
@ShadowRanger Do you know why `==` returns False? – S.B Jul 12 '22 at 12:39
@Bharel yes, but if it was just `__repr__` and had nothing to do with memory `L.extend();L = [L]; print(L);` would output the same as `L+L` – Axeltherabbit Jul 12 '22 at 12:59
@S.B: Where do you get the idea they're not equal to each other? The OP never performs an `==` comparison. They *are* equal to each other *if* you follow the `append`s with `e = l+l`, then `l.extend(l)`, then `e == l`. In that case, the outer `list` for `e` is a new `list`, but it's the same length as `l`, containing the same elements (`l`), and it compares equal. – ShadowRanger Jul 12 '22 at 13:10
@Axeltherabbit: Nope. `L + L` makes a new top-level `list` containing four references to the original `L`. `L.extend(L); L = [L]` creates a new top-level `list` containing *one* reference to the original `L` (which just happens to itself contain four references to itself one layer deeper). The latter just wraps an extra pair of brackets around what you see from the original `l.extend(l)` code (count the outer brackets), the former adds those outer brackets, but still has to display all four copies of `L`. – ShadowRanger Jul 12 '22 at 13:15
Ok @ShadowRanger , so isn't my point correct? it has nothing to do with `__repr__` but how it's saved in memory – Axeltherabbit Jul 12 '22 at 13:17
@ShadowRanger Yes OP didn't ask. I was playing with it : https://pastebin.pl/view/fac0d204 – S.B Jul 12 '22 at 13:20
1

@Axeltherabbit: "How it's saved in memory" is imprecise to the point of uselessness. It's "which `list`s are aliases and which are shallow copies?" and "are the operations mutating the aliased `list` or not?". `L + L` doesn't mutate `L` itself, `L.extend(L)` does. `__repr__` is short-cutting as soon as it detects recursion (a `list` containing an alias to itself). `L + L` delays that detection until it's descended twice, `L.extend(L)` detects it when it descends just once. – ShadowRanger Jul 12 '22 at 13:22
1

@S.B: Your version makes `res1 = l1 + l1` a length 2 `list` containing two aliases to the same length 1 `list` (each of which contain themselves recursively). While your `l2` is making a length 2 `list` containing *itself* (also a length 2 `list`) twice. They compare unequal because the first inner `list`'s lengths don't match (`1 != 2`). This is good; if you'd set it up so they did match lengths recursively, you'd have died with a `RecursionError` as it kept descending, never finding a `list` with differing lengths (it's not protected the way `__repr__` is). – ShadowRanger Jul 12 '22 at 13:27
1

If you do `l1 = []; l1.append(l1); l2 = []; l2.append(l2)`, then `l1 == l2`, it's a `RecursionError`. Comparing `l1` to itself (or to `[l1, l1]`) doesn't have the problem, returning `True` because the internal equality checking CPython uses for `list` has a special-case for when it's the same object being compared, immediately returning `True` without trying to recurse. If neither the length check special case nor the identity equals special case saves you though, comparing two inputs with recursive `list`s in them for equality recurses to death. – ShadowRanger Jul 12 '22 at 13:32

Why in Python a list self-reference doesn't behave the same way when extended or summed?

1 Answers1