CODEWITHSUNDEEP
python
csrankine
csrankine

Reputation: 73

Self-referencing lists

Say you do the following: 

a = [1]
a[0] = a

You end up with a as equal to [[...]]. What's going on here? How does this implicitly defined infinite chain of a's referring to a's end up as [[...]]?

Upvotes: 4

Views: 4979

Answers (3)

Gareth Rees
Gareth Rees

Reputation: 65854

You ain't seen nothing:

>>> a = []
>>> a[:] = [a] * 4
>>> a
[[...], [...], [...], [...]]

If you're interested in how this works in CPython, see list_repr in listobject.c and similar functions. Basically, any function that potentially prints a self-referential object calls Py_ReprEnter on the object before printing it and Py_ReprLeave when it is done. (See object.c for the definitions of these functions.) The former checks to see if the object is found in a thread-local stack of objects that are currently being printed (and if not, pushes it); the latter pops the object from the stack. So if Python is printing a list and discovers that the list is on the stack, that must mean that this is a self-referential list, and the list should be abbreviated, to avoid an infinite loop:

 i = Py_ReprEnter((PyObject*)v);
 if (i != 0) {
     return i > 0 ? PyString_FromString("[...]") : NULL;
 }

 // ...

 Py_ReprLeave((PyObject *)v);
 return result;

Upvotes: 9

NPE
NPE

Reputation: 500357

The list contains a reference to itself. The [[...]] is how this is rendered when you print the list.

The implementation goes out of its way to ensure it doesn't end up in an infinite recursion. It does this by rendering references to objects that are already being printed as [...].

This makes it work with indirect self-references too:

>>> a = []
>>> b = [a]
>>> a.append(b)
>>> a
[[[...]]]
>>> b
[[[...]]]

If you are really curious, you could study CPython's source code. In Python 2.7.3, the relevant code is located in Objects/listobject.c.

Upvotes: 4

Armin Rigo
Armin Rigo

Reputation: 12900

We have a == [a] here, so in theory a should be printed as a list containing one element, which is a --- i.e. itself a list containing one element, which is itself a list containing one element, and so on. Or in print: an infinite number of [, followed by an infinite number of ]. The fact that we get instead [[...]] is just Python trying to be helpful and not actually printing an infinite number of [.

Upvotes: 2

Related Questions