Is there any usage of self-referential lists or circular reference in list, eg. appending a list to itself

Question

So if I have a list a and append a to it, I will get a list that contains it own reference.

>>> a = [1,2]
>>> a.append(a)
>>> a
[1, 2, [...]]
>>> a[-1][-1][-1]
[1, 2, [...]]

And this basically results in seemingly infinite recursions.

And not only in lists, dictionaries as well:

>>> b = {'a':1,'b':2}
>>> b['c'] = b
>>> b
{'a': 1, 'b': 2, 'c': {...}}

It could have been a good way to store the list in last element and modify other elements, but that wouldn't work as the change will be seen in every recursive reference.

I get why this happens, i.e. due to their mutability. However, I am interested in actual use-cases of this behavior. Can somebody enlighten me?

Answer 1

The use case is that Python is a dynamically typed language, where anything can reference anything, including itself.

List elements are references to other objects, just like variable names and attributes and the keys and values in dictionaries. The references are not typed, variables or lists are not restricted to only referencing, say, integers or floating point values. Every reference can reference any valid Python object. (Python is also strongly typed, in that the objects have a specific type that won't just change; strings remain strings, lists stay lists).

So, because Python is dynamically typed, the following:

foo = []
# ...
foo = False

is valid, because foo isn't restricted to a specific type of object, and the same goes for Python list objects.

The moment your language allows this, you have to account for recursive structures, because containers are allowed to reference themselves, directly or indirectly. The list representation takes this into account by not blowing up when you do this and ask for a string representation. It is instead showing you a [...] entry when there is a circular reference. This happens not just for direct references either, you can create an indirect reference too:

>>> foo = []
>>> bar = []
>>> foo.append(bar)
>>> bar.append(foo)
>>> foo
[[[...]]]

foo is the outermost [/]] pair and the [...] entry. bar is the [/] pair in the middle.

There are plenty of practical situations where you'd want a self-referencing (circular) structure. The built-in OrderedDict object uses a circular linked list to track item order, for example. This is not normally easily visible as there is a C-optimised version of the type, but we can force the Python interpreter to use the pure-Python version (you want to use a fresh interpreter, this is kind-of hackish):

>>> import sys
>>> class ImportFailedModule:
...     def __getattr__(self, name):
...         raise ImportError
...
>>> sys.modules["_collections"] = ImportFailedModule()  # block the extension module from being loaded
>>> del sys.modules["collections"]  # force a re-import
>>> from collections import OrderedDict

now we have a pure-python version we can introspect:

>>> od = OrderedDict()
>>> vars(od)
{'_OrderedDict__hardroot': <collections._Link object at 0x10a854e00>, '_OrderedDict__root': <weakproxy at 0x10a861130 to _Link at 0x10a854e00>, '_OrderedDict__map': {}}

Because this ordered dict is empty, the root references itself:

>>> od._OrderedDict__root.next is od._OrderedDict__root
True

just like a list can reference itself. Add a key or two and the linked list grows, but remains linked to itself, eventually:

>>> od["foo"] = "bar"
>>> od._OrderedDict__root.next is od._OrderedDict__root
False
>>> od._OrderedDict__root.next.next is od._OrderedDict__root
True
>>> od["spam"] = 42
>>> od._OrderedDict__root.next.next is od._OrderedDict__root
False
>>> od._OrderedDict__root.next.next.next is od._OrderedDict__root
True

The circular linked list makes it easy to alter the key ordering without having to rebuild the whole underlying hash table.

Answer 2

However, I am interested in actual use-cases of this behavior. Can somebody enlighten me?

I don't think there are many useful use-cases for this. The reason this is allowed is because there could be some actual use-cases for it and forbidding it would make the performance of these containers worse or increase their memory usage.

Python is dynamically typed and you can add any Python object to a list. That means one would need to make special precautions to forbid adding a list to itself. This is different from (most) typed-languages where this cannot happen because of the typing-system.

So in order to forbid such recursive data-structures one would either need to check on every addition/insertion/mutation if the newly added object already participates in a higher layer of the data-structure. That means in the worst case it has to check if the newly added element is anywhere where it could participate in a recursive data-structure. The problem here is that the same list can be referenced in multiple places and can be part of multiple data-structures already and data-structures such as list/dict can be (almost) arbitrarily deep. That detection would be either slow (e.g. linear search) or would take quite a bit of memory (lookup). So it's cheaper to simply allow it.

The reason why Python detects this when printing is that you don't want the interpreter entering an infinite loop, or get a RecursionError, or StackOverflow. That's why for some operations like printing (but also deepcopy) Python temporarily creates a lookup to detect these recursive data-structures and handles them appropriately.